$$\LARGE{\color{Orange}{\mathbf{Note-各种题目收录} } }$$
带权并查集:
题意:给出 $n$ 个点,要求构造合法的完全图,已经给出了一些边。
边有爱边和恨边,其中任意三个点,连成的边合法的组合有爱爱爱,爱恨恨。
爱边定义为 $1$,恨边定义为 $0$ ,问符合要求的完全图的数量,对 $1e9+7$取模
-
如果将爱边定义为 $0$,恨边定义为 $1$,那么合法的三组边只需满足其异或和为 $0$。
-
对于这个题,相当于,我们要构造一个完全图,使得其任意三元环都满足其三条边异或和为 $0$
Note: 我们知道对于一个异或和为定值的环,如果确定了其中两条边,那么另外一条边也确定了。
key1. 注意到,如果 $a$ 与 $b$ 之间的边的值为 $c$,意味着:
$$edge[a,a +1] \mathbf{\;xor\;} edge[a + 1,a + 2] \mathbf{\;xor\;} \cdots \mathbf{\;xor\;} edge[b-1,b] = c$$
Proof.这是因为三元环的异或和为0的性质:
\begin{align}
&edge[a,a +1] \mathbf{\;xor\;} edge[a + 1,a + 2] \mathbf{\;xor\;} \cdots \mathbf{\;xor\;} edge[b-1,b] = c\\
&\;\\
&=edge[a,a + 2]\mathbf{\;xor\;} \cdots \mathbf{\;xor\;} edge[b-1,b]\\
&\;\\
&= edge[a,b] = c
\end{align}
key2. 再考虑到可以使用异或前缀和,将上述区间异或和,转换为讨论两个边$b - 1,a - 1$异或
- 使用 $d$ 数组维护在同一个并查集两个边的相对异或值,于是:
$$\mbox{a,b的边值为c} \rightarrow d[a] \mathbf{\;xor\;} d[b] = c$$
- 如果两个点不在同一并查集,则合并两个点。
因为在同一集合的边,只需要确定集合里的一条边的取值,就能推出其他边的取值
设集合的数量为 $k$,考虑到一条边的取值有两种选择,所以完全图的数量为:
$$2^{k - 1}$$
减一的原因是,前 $0$ 个边的异或和为0,所以其值已经确定,所以与 $0$ 在同一集合的边的值已经确定。
code
// LUOGU_RID: 109837073
#include <bits/stdc++.h>
#define fastio() ios::sync_with_stdio(0),\
cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;
typedef long long LL;
constexpr int N = 100010;
constexpr int mod = 1e9 + 7;
int p[N],d[N];
int find(int x)
{
if(p[x] != x)
{
int ro = find(p[x]);
d[x] ^= d[p[x]];
p[x] = ro;
}
return p[x];
}
LL qmi(LL a,int b)
{
LL res = 1;
while(b)
{
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main()
{
fastio();
int n,m;cin >> n >> m;
for(int i = 1;i <= n;i ++ ) p[i] = i;
int sz = n;
bool suc = 1;
while(m -- )
{
int a,b,c;
cin >> a >> b >> c;
c ^= 1;
int pa = find(a - 1),pb = find(b - 1);
if(pa == pb && d[a - 1] ^ d[b - 1] != c) suc = 0;
else if(pa != pb)
{
d[pb] = d[a - 1] ^ c ^ d[b - 1];
p[pb] = pa;
sz --;
}
}
if(!suc) cout << 0 << endl;
else cout << qmi(2,sz - 1) << endl;
return 0;
}