题解：UVA1607 与非门电路 Gates

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node {
	int u,v,w;
} a[1000001];
int n,m;
int fun(int u) {
	for (int i=n-u; i<n; i++){
		a[i].w=1;
	}
	for (int i=0; i<n-u; i++) a[i].w=0;
	for (int i=n+1; i<=n+m; i++) {
		a[i].w=!(a[a[i].u].w&a[a[i].v].w);
	}
	return a[m+n].w;
}
signed main() {
	memset(a,0,sizeof(a));
	int T;
	cin>>T;
	for(t--) {
		cin>>n>>m;
		memset(a,0,sizeof(a));
		for (int i=1; i<=m; i++) {
			int u,v;
			cin>>u>>v;
			a[n+i].u=u+n;//存入 
			a[n+i].v=v+n;
		}
		int x=fun(0);
		int a1=fun(n),ans;
		if (x==y)ans=0;
		else {
			int L=0,R=n;
			while(L<R) {
				int mid=(L+R)/2;
				if (fun(mid)==y){
					R=mid;//找到了当前的答案 
				}
				else{
					L=mid+1;//说明答案右边 
				} 
			}
			ans=L;
		}
		for (int i=1; i<ans; i++){//输出答案 
			cout<<1;
		} 
		if (ans>=1){
			cout<<"x";
		}
		for (int i=ans+1; i<=n; i++){
			cout<<0;
		}
		cout<<endl;
	}
}