题意:有\(n\)个点和\(m\)条无向边,现在让你给你这\(m\)条边赋方向,但是要满足任意一条边的路径都不能大于\(1\),问是否有满足条件的构造方向,如果有,输出一个二进制串,表示所给的边的方向.

题解:我们先单独拿出\(3\)个点来看,选择一个点,那么与它相连的另外两个点到自己的方向一定是相同的,同理,我们可以推广到任意一个点,与它相连的所有点到它的方向必须都是一样的才行,其实到这儿就不难看出可以用二分图染色来写了,然后打个板子就能很愉快的AC啦~

代码:

int n,m;

int a,b;

vector<int> v[N];

int color[N];

PII edge[N];

bool dfs(int u,int c){

	color[u]=c;

	for(auto w:v[u]){

		if(!color[w]){

			if(!dfs(w,3-c)) return false;

		}

		else{

			if(color[w]==c) return false;

		}

	}

	return true;

}

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>n>>m;

    rep(i,1,m){

    	cin>>a>>b;

    	edge[i].fi=a;

    	edge[i].se=b;

    	v[a].pb(b);

    	v[b].pb(a);

    }

    bool flag=true;

   	if(!dfs(1,1)){

   		flag=false;

   	}

   	if(!flag) cout<<"NO\n";

   	else{

   		cout<<"YES\n";

   		rep(i,1,m){

   			int x=edge[i].fi;

   			int y=edge[i].se;

   			if(color[x]==1 && color[y]==2) cout<<1;

   			else cout<<0;

   		}

   	}

    return 0;

}