CF553C Love Triangles

题目描述:

给出

边有爱边和恨边，其中任意三个点，连成的边合法的组合有爱爱爱，爱恨恨。

题解：

根据朋友的朋友是朋友，敌人的敌人是朋友这个道理，是构造合法二分图，二分图可以用染色法和并查集判。然后会有k个联通块，把联通快想成点以后，又需要成为二分图，每个联通块之间确认第一条边后，状态就被确定了。所有方案数是2的(k-1)次。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N = 4e5 + 10;
 5 const int M = 2e5 + 10;
 6 const ll mod = 1e9 + 7;
 7 inline int read()
 8 {
 9     int x = 0, f = 1; char ch = getchar();
10     while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
11     while(ch <= '9' && ch >= '0') {    x = (x << 1) + (x << 3) + ch -'0';ch = getchar();}
12     return x * f;
13 }
14  
15 int n, m, q;
16 int p[N], d[N];
17  
18 int find(int x)
19 {
20     if(p[x] == x) return x;
21     int t = find(p[x]);
22     d[x] ^= d[p[x]];
23     return p[x] = t;
24 }
25  
26 int main()
27 {
28     n = read(), m = read();
29     for (int i = 1; i <= n; i ++) p[i] = i;
30     for (int i = 1; i <= m; i ++)
31     {
32         int x = read(), y = read(), w= read() ^ 1;
33         int fx = find(x), fy = find(y);
34         int t = d[x] ^ d[y] ^ w;
35         if(fx != fy)
36         {
37             p[fx] = fy;
38             d[fx] = t;
39         }
40         else if(t & 1)
41         {
42             puts("0");
43             return 0;
44         }
45     }
46     int res = 0;
47     for (int i = 1; i <= n; i ++)
48     {
49         if(find(i) == i)
50         {
51             res ++;
52         }
53     }
54     ll ans = 1;
55     for (int i = 0; i < res - 1; i ++)
56         ans = ans * 2 % mod;
57     cout << ans << '
';
58 }

View Code