开始时,每个节点的根均为自己,进行合并的过程就是进行被加入节点根转移的过程
其中的?就是用于修正根转移之后的偏移量(为使合并后原集合节点仍保持正确的意义)
例如同类时:d[x]+? ≡ d[y],即?≡d[y]-dx
又因为是根转移因此:d[px]+=?
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int p[N], d[N];//d[x]表示:x到父节点的距离(经路径压缩后才为到root的距离)
int find(int x)
{
if (p[x] != x)
{
int t = p[x];
p[x] = find(p[x]);
d[x] += d[t];//经过路径压缩后,p[t]一定为root,因此d[t]表示为父节点到root的距离
}
return p[x];
}
int main()
{
int res = 0;
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++)p[i] = i;
while (k--)
{
int D, x, y; cin >> D >> x >> y;
int px = find(x), py = find(y);
if (x > n || y > n) { res++; continue; }
if (D == 2 && x == y) { res++; continue; }//不加continue就会多计数
if (px != py)
{
if (D == 1)//同类合并
{
d[px] += d[y] - d[x];
p[px] = py;
}
else if (D == 2)//捕食合并
{
d[px] += -1 + d[y] - d[x];
p[px] = py;
}
}
else
{
if (D == 1 && (d[x] - d[y]) % 3 != 0)res++;
if (D == 2 && (d[x] + 1 - d[y]) % 3 != 0)res++;
}
}
cout << res;
}
Python
N = 50010
p = [i for i in range(N)]
d = [0] * N
def find(x):
if p[x] != x:
t = p[x]
p[x] = find(p[x])
d[x] += d[t]
return p[x]
res = 0
n, k = map(int, input().split())
while k:
k -= 1
D, x, y = map(int, input().split())
if D == 2 and x == y: res += 1
elif x > n or y > n: res += 1
else:
px, py = find(x), find(y)
if px != py:
if D == 1:
d[px] += d[y] - d[x]
p[px] = py
else:
d[px] += d[y] - d[x] - 1
p[px] = py
else:
if D == 1 and d[x] % 3 != d[y] % 3: res += 1
if D == 2 and (d[x] + 1) % 3 != d[y] % 3: res += 1
print(res)