出题人题解 | #定向#

原题解链接：https://ac.nowcoder.com/discuss/149978

$dfsd\; f\; s$ 出一棵生成树，令所有树边从父亲指向儿子，所有返祖边从后代指向祖先。

判断这样构造的有向图是否强连通即可。

正确性证明如下:

如果无向图不连通或者存在割边显然无解，

否则这样构造一定是一组解。

因为考虑 $tarjantarjan$ 求割边的过程，不存在割边就意味着每个点都能走回他的祖先，

所以在这样构造的有向图里，每个点也依旧能走回他的祖先。

#include<bits/stdc++.h>
using namespace std;

template <typename T> void chmin(T &x,const T &y)
{
	if(x>y)x=y;
}
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=1e6+5,M=1e6+5;
int t[N];
struct Edge
{
	int to,next;
};
Edge l[M*2];
int dfn[N],low[N],tot;
bool b[M];

void out()
{
	puts("impossible");
	exit(0);
}

void dfs(int x,int fr)
{
	dfn[x]=low[x]=++tot;
	for(int i=t[x];i;i=l[i].next)
	{
		int y=l[i].to;
		if(y==fr)continue;
		if(dfn[y])
		{
			chmin(low[x],low[y]);
			if(dfn[y]<dfn[x])b[i/2]=i%2^1;
		}
		else
		{
			b[i/2]=i%2^1;
			dfs(y,x);
			chmin(low[x],low[y]);
		}
	}
}

int main()
{
	int n,m;
	cin>>n>>m;
	rep(i,1,m)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		l[i*2]=(Edge){y,t[x]};t[x]=i*2;
		l[i*2+1]=(Edge){x,t[y]};t[y]=i*2+1;
	}
	dfs(1,0);
	rep(i,2,n)
	if(low[i]>=dfn[i])out();
	rep(i,1,m)putchar('0'+b[i]);	
}