Love Triangles(带权并查集)

描述

传送门:Codeforces554E

There are many anime that are about “love triangles”: Alice loves Bob, and Charlie loves Bob as well, but Alice hates Charlie. You are thinking about an anime which has $n$ characters. The characters are labeled from $1$ to $n$. Every pair of two characters can either mutually love each other or mutually hate each other (there is no neutral state).

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 $a_i, b_i, c_i$. If $c_i$ is $1$, then $a_i$ and $b_i$ are in love, otherwise, they hate each other $(1 ≤ a_i, b_i ≤ n, a_i ≠ b_i,c_i\in \lbrace 0,1 \rbrace )$.

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$.

Examples

  • input
1
3 0
  • output
1
4
  • input
1
2
3
4
5
4 4
1 2 1
2 3 1
3 4 0
4 1 0
  • output
1
1
  • input
1
2
3
4
5
4 4
1 2 1
2 3 1
3 4 0
4 1 1
  • output
1
0

Note

In the first sample, the four ways are to:

  • Make everyone love each other
  • Make 1 and 2 love each other, and 3 hate 1 and 2 (symmetrically, we get 3 ways from this).

In the second sample, the only possible solution is to make 1 and 3 love each other and 2 and 4 hate each other.

思路

  • 题意:给出一个无向图,求有多少方案使得其成为一个完全图,使得任意三个人满足:
    A喜欢B,B喜欢C,A喜欢C;
    或者A讨厌B,B讨厌C,A喜欢C。

  • 我们可以发现,三个人之间只要知道两个关系,第三个关系就可以唯一确定。如果设喜欢为$0$,不喜欢为$1$的话,恰好是一个异或的关系。

$\oplus$ $0$ $1$ 备注
$0$ $0$ $1$ 喜欢+喜欢=喜欢
喜欢+不喜欢=不喜欢
$1$ $1$ $0$ 不喜欢+喜欢=不喜欢
不喜欢+不喜欢=喜欢
  • 于是我们考虑用带权并查集去维护每个人之间的关系,$val[]$数组记录它与父亲结点的关系,$0$表示喜欢,$1$表示不喜欢。
  • 如果输入的关系存在矛盾,那么答案就是$0$,否则我们考虑方案数:由于在一个集合中的人的关系都是唯一确定的,所以对于每一个独立的集合,只有一种方案;而对于不同的集合,只要两个根结点的关系确定,两个集合所有人的关系也是唯一确定了。于是我们得到答案应该为$2^{k-1}$,$k$为集合的个数。
  • $2^{k-1}$可以用快速幂算,也可以令答案初始值为$\frac{1}{2}$,($inv(2)$),然后每一个独立的集合乘以$2$.
  • 注意题目输入的数据中,$1$是喜欢,$0$是不喜欢,记得做并查集的时候要反一下。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
#define clr(a,x) memset(a, x, sizeof(a))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int maxn = 1e5 + 5;
int par[maxn], val[maxn];

void init(int n)
{
for (int i = 1; i <= n; i++)
par[i] = i, val[i] = 0;
}

int find(int x)
{
if (par[x] == x) return x;
int tmp = find(par[x]);
val[x] ^= val[par[x]];
return par[x] = tmp;
}

int main()
{
fastin
int n, m;
cin >> n >> m;
init(n);
while (m--)
{
int u, v, w;
cin >> u >> v >> w;
int t1 = find(u), t2 = find(v);
if (t1 != t2)
{
val[t2] = val[u] ^ val[v] ^ w ^ 1;
par[t2] = t1;
}
else
{
if (val[u] == val[v] && w == 0)
{
puts("0");
return 0;
}
if (val[u] != val[v] && w == 1)
{
puts("0");
return 0;
}
}
}
ll ans = (mod - mod / 2) % mod;
for (int i = 1; i <= n; i++)
if (find(i) == i)
ans = (ans + ans) % mod;
cout << ans << endl;
return 0;
}
捐助作者