题意：给出n个人，这n个人要么相互喜欢，要么相互憎恨，现在给出其中一部分关系，要求完成剩下的关系，使其满足以下关系：不能有三个人互相都是憎恨，也不能有三个人有两个爱着其中一个人而这两个人相互憎恨。问在给定条件下剩下的关系有多少种指定方法。
思路：首先，相互喜欢的联通块是可以直接合并成一个点的，因为其他任意一点对于联通快内的点要么都是憎恨，要么都是喜欢，而联通快内的点剩下的边必然都是喜欢，否则违反规定。剩下的就是不同联通块之间的关系，指定关系后必然形成一个二分图，如果已经有的边违反了二分图的性质（不能有奇圈），那么答案为0，否则答案为2^联通块的个数。
（证明：如果有奇圈，那么相隔一个的两个人必然相恋，但是因为这是一个奇圈，必然导出矛盾）
又：这个题要合并点，但是想了好久没有想出合适的较简单的写法，后来看了下标程。。其实在读入边之后直接处理就好了。
#include<iostream> #include<map> #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> #include<vector> #include<queue> #include<stack> #include<functional> #include<set> #define pb push_back using namespace std; typedef long long ll; const int maxv=100040; const int mod=1e9+7; int fa[maxv]; int findFa(int x){ if(fa[x]==x) return x; return fa[x]=findFa(fa[x]); } bool same(int x,int y){ return findFa(x)==findFa(y); } void unite(int x,int y){ if(same(x,y)) return; fa[findFa(x)]=findFa(y); } struct edge{ int f,t; bool v; }; edge es[maxv]; vector<int> G[maxv]; bool col[maxv]; bool vis[maxv]; bool dfs(int u,bool c){ vis[u]=1; col[u]=c; int flag=1; for(int i=0;i<G[u].size();i++){ int t=G[u][i]; if(vis[t]&&col[t]==col[u]) return 0; if(!vis[t]) flag&=dfs(t,!c); } return flag; } int qpow(int x,int p){ ll xx=x,ans=1; while(p>0){ if(p&1) ans=(ans*xx)%mod; xx=(xx*xx)%mod; p>>=1; } return ans; } int n,m; int main(){ for(int i=0;i<maxv;i++) fa[i]=i; cin>>n>>m; for(int i=0;i<m;i++){ int f,t,v; scanf("%d%d%d",&f,&t,&v); es[i]=(edge){f,t,v}; if(v) unite(f,t); } for(int i=0;i<m;i++){ edge &e=es[i]; if(!e.v){ G[findFa(e.f)].pb(findFa(e.t)); G[findFa(e.t)].pb(findFa(e.f)); } } int cont=0; int flag=1; for(int i=1;i<=n;i++){ if(findFa(i)==i&&!vis[findFa(i)]){ cont++; flag&=dfs(i,0); } } if(flag){ cout<<qpow(2,cont-1)<<endl; }else{ cout<<0<<endl; } return 0; }