题意:训练指南P191
分析:本题特殊,n个物品,n种元素则会爆炸,可以转移到图论里的n个点,连一条边表示u,v元素放在一起,如果不出现环,一定是n点,n-1条边,所以如果两个元素在同一个集合就会爆炸.
#include <bits/stdc++.h>
using namespace std; const int N = 1e5 + 5;
struct DSU {
int rt[N], rk[N];
void init(void) {
memset (rt, -1, sizeof (rt));
memset (rk, 0, sizeof (rk));
}
int Find(int x) {
return rt[x] == -1 ? x : rt[x] = Find (rt[x]);
}
void Union(int x, int y) {
x = Find (x); y = Find (y);
if (x == y) return ;
if (rk[x] > rk[y]) {
rt[y] = x; rk[x] += rk[y] + 1;
}
else {
rt[x] = y; rk[y] += rk[x] + 1;
}
}
bool same(int x, int y) {
return Find (x) == Find (y);
}
}dsu; int main(void) {
dsu.init ();
int ans = 0, x, y;
while (scanf ("%d", &x) == 1) {
if (x == -1) {
printf ("%d\n", ans);
dsu.init (); ans = 0;
continue;
}
scanf ("%d", &y);
if (dsu.same (x, y)) ans++;
else dsu.Union (x, y);
} return 0;
}