C. Love Triangles
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/553/problem/C
Description
You hate love triangles (A-B are in love and B-C are in love, but A-C hate each other), and you also hate it when nobody is in love. So, considering any three characters, you will be happy if exactly one pair is in love (A and B love each other, and C hates both A and B), or if all three pairs are in love (A loves B, B loves C, C loves A).
You are given a list of m known relationships in the anime. You know for sure that certain pairs love each other, and certain pairs hate each other. You're wondering how many ways you can fill in the remaining relationships so you are happy with every triangle. Two ways are considered different if two characters are in love in one way but hate each other in the other. Print this count modulo 1 000 000 007.
Input
The first line of input will contain two integers n, m (3 ≤ n ≤ 100 000, 0 ≤ m ≤ 100 000).
The next m lines will contain the description of the known relationships. The i-th line will contain three integers ai, bi, ci. If ci is 1, then ai and bi are in love, otherwise, they hate each other (1 ≤ ai, bi ≤ n, ai ≠ bi, ).
Each pair of people will be described no more than once.
Output
Print a single integer equal to the number of ways to fill in the remaining pairs so that you are happy with every triangle modulo 1 000 000 007.
Sample Input
4 4
1 2 1
2 3 1
3 4 0
4 1 0
Sample Output
1
HINT
题意
给你一个无向图，然后要求让你添上边变成完全图，要求任意3元环都不是三角恋关系，或者没人相爱
然后问你方案数
题解：
考虑1号点连出去的所有边，有n-1条，事实上，这n-1条的颜色，就决定了整个图形的颜色。
原因在于，我们先假设两个人相爱，就涂红边，否则涂蓝边。
从n-1条中拿出两条(1, x)和(1, y)，那么如果(1, x)和(1, y)都是红色，或者都是蓝色，那么(x, y) 一定是红色。
否则(x, y)就是蓝色。
那么给出任意一条边的信息(x, y)的颜色，就决定了(1, x) 和 (1, y) 是同色还是异色。那么就转化成这样一个问题，有n-1个点的无向图，要把点染成黑白色，给出部分点对是同色还是异色，求方案数
那么基本就是个简单的dfs了
代码
//qscqesze #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define maxn 2000001 #define mod 1000000007 #define eps 1e-9 int Num; char CH[20]; const int inf=0x3f3f3f3f; inline ll read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //************************************************************************************** vector< pair<int,int> > e[maxn]; int vis[maxn]; int ans; void dfs(int x) { for(int i=0;i<e[x].size();i++) { int v=e[x][i].first; int t=e[x][i].second; if(vis[v]==-1) { if(t==1) vis[v]=vis[x]; else vis[v]=1-vis[x]; dfs(v); } if(t==1) { if(vis[v]!=vis[x]) ans=0; } else { if(vis[v]==vis[x]) ans=0; } } } int main() { int n=read(),m=read(); for(int i=0;i<m;i++) { int a=read(),b=read(),c=read(); e[a].push_back(make_pair(b,c)); e[b].push_back(make_pair(a,c)); } ans=(mod+1)/2; memset(vis,-1,sizeof(vis)); for(int i=1;i<=n;i++) { if(vis[i]==-1) { ans=(ans+ans)%mod; vis[i]=0; dfs(i); } } cout<<ans<<endl; }