带权并查集

inline int f(int x) {
if(x ^ fa[x]) {
int t = fa[x];
fa[x] = f(fa[x]);
cnt[x] += cnt[t];
}
return fa[x];
}

How Many Answers Are Wrong HDU - 3038

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <cstring>
#include <algorithm>
#define rint register int
#define ll long long
#define lson x<<1
#define rson x<<1|1
#define mid ((st[x].l + st[x].r) >> 1)
using namespace std;
template <typename xxx> inline void read(xxx &x)
{
int f = 1;x = 0;
char c = getchar();
for(; c < '0' || c > '9' ; c = getchar()) if(c=='-') f = -1;
for(;'0' <= c && c <= '9'; c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
x *= f;
}
template <typename xxx> inline void print(xxx x)
{
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9) print(x/10);
putchar(x % 10 + '0');
}
const int inf = 0x7fffffff;
const int maxn = 200100;
const int mod = 1000000007;
int n,m;
int fa[maxn];
int cnt[maxn];//自身到集合代表的权值
inline int f(int x) {
if(x ^ fa[x]) {
int t = fa[x];
fa[x] = f(fa[x]);
cnt[x] += cnt[t];
}
return fa[x];
}
int main()
{
while(~scanf("%d%d",&n,&m)) {
for(rint i = 1;i <= n; ++i) {
fa[i] = i;
cnt[i] = 0;
}
int ans = 0;
for(rint i = 1;i <= m; ++i) {
int x,y,z;
--x;
int fx = f(x);
int fy = f(y);
if(fx == fy) {
if(cnt[x] - cnt[y] != z) ++ans;
}
else {
fa[fx] = fy;
cnt[fx] = cnt[y] - cnt[x] + z;
}
}
print(ans);putchar('\n');
}
}
/*

*/