Description：

给一个有完美匹配的二分图，询问每条边是否一定在完美匹配中。

$1\leqslant n\leqslant 2\times 10^5,1\leqslant m\leqslant 6\times 10^5$

Solution：

这题没过，因为网上唯一一份题解还是 $pascal$ 的。

首先我们需要求出一个完美匹配，这个可以用 $dinic$ 达到 $O(n\sqrt m)$ 的复杂度，然后对于匹配边从左到右，非匹配边从右到左，这样建出边后求出强连通分量，在强连通分量中的边就是可以不在完美匹配中的边。

Code：

#include

#include

#include

#include

#include

#include

#include

using namespace std;

inline int rd()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,m;

#define MAXN 400010

#define MAXM 600010

int u[MAXM],v[MAXM];

int match[MAXN];

int vis[MAXN],tim = 0;

struct edge

{

	int to,nxt;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

bool find(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to] != tim)

		{

			vis[e[i].to] = tim;

			if(match[e[i].to] == -1 || find(match[e[i].to]))

			{

				match[e[i].to] = k;

				return true;

			}

		}

	}

	return false;

}

namespace TARJAN

{

	struct edge

	{

		int to,nxt;

	}e[MAXM];

	int edgenum = 0;

	int lin[MAXN] = {0};

	inline void add(int a,int b)

	{

		e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

		return;

	}

	int dfn[MAXN],low[MAXN],tot = 0;

	int stack[MAXN],top = 0;

	bool v[MAXN];

	int ins[MAXN],scc = 0;

	void tarjan(int k)

	{

		dfn[k] = low[k] = ++tot;

		stack[++top] = k;v[k] = true;

		for(register int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(dfn[e[i].to] == 0)

			{

				tarjan(e[i].to);

				low[k] = min(low[k],low[e[i].to]);

			}

			else if(v[e[i].to])

			{

				low[k] = min(low[k],dfn[e[i].to]);

			}

		}

		if(low[k] >= dfn[k])

		{

			register int t;++scc;

			do

			{

				t = stack[top--];

				ins[t] = scc;v[t] = false;

			}while(t != k);

		}

		return;

	}

	void solve()

	{

		for(register int i = 1;i <= 2 * n;++i)

		{

			if(dfn[i] == 0)tarjan(i);

		}

		return;

	}

}

int main()

{

	scanf("%d%d",&n,&m);

	for(register int i = 1;i <= m;++i)

	{

		u[i] = rd();v[i] = rd();

		add(u[i],v[i]);

	}

	memset(match,-1,sizeof(match));

	for(int i = 1;i <= n;++i)

	{

		++tim;

		find(i);

	}

	for(int i = 1;i <= m;++i)

	{

		if(u[i] == match[v[i]])

			TARJAN::add(u[i],v[i] + n);

		else

			TARJAN::add(v[i] + n,u[i]);

	}

	TARJAN::solve();

	for(register int i = 1;i <= m;++i)

	{

		if(TARJAN::ins[u[i]] == TARJAN::ins[v[i] + n])putchar('0');

		else if(match[v[i]] == u[i])putchar('1');

		else putchar('2');

	}

	puts("");

	return 0;

}