UVa 1160 - X-Plosives
传送门
题意
一个化合物由两种元素组成，如果有N个化合物N个元素就会爆炸，求不能加入的数目。
思路
把每个元素看成顶点，一个化合物就是一条边，图存在环的时候就不行，则题目就变成了求加入变成环的化合物的数目。
用并查集
代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int p[MAXN];
int FindSet(int x)
{
return p[x] == x ? x : p[x] = FindSet(p[x]);
}
int main()
{
//freopen("input.txt", "r", stdin);
int x, y, i, j, ans;
while (~scanf("%d", &x))
{
ans = 0;
for (i = 0; i < MAXN; i++)
p[i] = i;
while (x != -1)
{
scanf("%d", &y);
x = FindSet(x), y = FindSet(y);
if (x == y)
ans++;
else
p[x] = y;
scanf("%d", &x);
}
printf("%d\n", ans);
}
return 0;
}