题目：CF741C Arpa’s overnight party and Mehrdad’s silent entering
一看两种颜色很明显就是二分图点染色问题了。
关键在于建图。很明显我们把情侣之间连一条边因为颜色不能一样。相邻三个之间只要把左右两两建边强制为不同的就行了。
1 #include<cstdio> 2 #define it register int 3 #define il inline 4 const int N=2000005; 5 int n,m,h[N],nxt[N],adj[N],u[N],v[N],t,col[N]; 6 bool fl=0; 7 il void add(it u,it v){ 8 nxt[++t]=h[u],h[u]=t,adj[t]=v; 9 nxt[++t]=h[v],h[v]=t,adj[t]=u; 10 } 11 void fr(int &num){ 12 num=0;char c=getchar();int p=1; 13 while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar(); 14 while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar(); 15 num*=p; 16 } 17 il void dfs(it x){ 18 if(fl) return; 19 for(it i=h[x];i;i=nxt[i]){ 20 if(col[adj[i]]==col[x]){fl=1;return;} 21 if(!col[adj[i]]) col[adj[i]]=col[x]^3,dfs(adj[i]); 22 } 23 } 24 int main(){ 25 fr(n),m=n<<1; 26 for(it i=1;i<=n;++i) fr(u[i]),fr(v[i]),add(u[i],v[i]); 27 for(it i=1;i<=n;++i) add(2*i-1,2*i),add(2*i,2*i-1); 28 for(it i=1;i<=m;++i) if(!col[i]) col[i]=1,dfs(i); 29 dfs(1); 30 if(fl) return puts("-1"),0; 31 for(it i=1;i<=n;++i) printf("%d %d ",col[u[i]],col[v[i]]); 32 return 0; 33 }