C++(clang++11) 解法, 执行用时: 9ms, 内存消耗: 476K, 提交时间: 2020-12-18 10:01:23

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
struct edge{
	int to,nxt,id;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v,int id)
{
	d[++cnt] = (edge){v,head[u],id},head[u] = cnt;
}
int dfn[maxn],low[maxn],id,vis[maxn],flag=1,n,m;
void tarjan(int u,int fa)
{
	low[u] = dfn[u] = ++id;
	int F = 0;
	for(int i=head[u];i;i=d[i].nxt )
	{
		int v = d[i].to;
		if( !dfn[v] )
		{
			tarjan(v,u);
			if( low[v]>dfn[u] )	flag = 0;//存在桥 
			low[u] = min( low[u],low[v] );
			vis[i/2] = d[i].id;
		}
		else
		{
			if( F || v!=fa )
			{
				if( low[u]>dfn[v] )	
					low[u] = dfn[v],vis[i/2] = d[i].id;
			}
			else	F = 1;
		}
	}
}
int main()
{
	cin >> n >> m;
	for(int i=1;i<=m;i++)
	{
		int l,r; scanf("%d%d",&l,&r);
		add(l,r,1); add(r,l,0);
	}
	tarjan(1,0);
	if( flag==0 )	cout << "impossible";
	else
	{
		for(int i=1;i<=m;i++)	printf("%d",vis[i]);
	}
}