# 并查集--带权

```
```
```
```
```
```
```
```
```
```
`并查集:节点到个节点的距离dis[i]；`
```
```
```
```
```#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

const int N = 10e5+5;

int bleg[N], dis[N];

int find (int x)
{
int y = x, cnt=0;
while (y != bleg[y])
{
cnt += dis[y];
y = bleg[y];
}
while (x != bleg[x])
{
int px = bleg[x];
int tp = dis[x];
dis[x] = cnt;
bleg[x] = y;
cnt -= tp;
x = px;
}
return y;
}

void Union(int a, int b)
{
int pa = find (a), pb = find (b);
if (pa == pb) return;

if (rand()%2)
{
bleg[pa] = pb;
dis[pa] = dis[a] + dis[b] + 1;
}
else
{
bleg[pb] = pa;
dis[pb] = dis[a] + dis[b] + 1;
}
}

void Init (int n)
{
for (int i=1; i<=n; i++)
bleg[i] = i, dis[i] = 0;
}

void question (int a, int b)
{
int pa = find (a), pb = find (b);
if (pa == pb)
{
if ((dis[a]+dis[b])%2)
puts ("In different gangs.");
else
puts ("In the same gang.");
}
else
puts ("Not sure yet.");
}

int main ()
{
int t, n, m, a, b;
char c;
scanf ("%d",&t);
while (t--)
{
scanf ("%d%d",&n,&m);
Init (n);
for (int i=0; i<m; i++)
{
scanf (" %c %d %d",&c,&a,&b);
if (c == 'A')
question (a, b);
else
Union (a, b);
}
}
return 0;
}```