每种化合物由2中元素组成
现在要按照顺序装化合物 如果装的个数等于元素的种类 那么不可以装 求有多少个不可以装
输入的是每种化合物的2种元素 每个元素看成点 每个化合物连城一条边 那么等价于点数等于边数 就是环 用并查集判断环
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
const int maxn = 100010;
using namespace std;
int pa[maxn];
int find(int x)
{
if(x != pa[x])
return pa[x] = find(pa[x]);
return pa[x];
}
int main()
{
int x, y;
while(scanf("%d", &x) == 1)
{
int cnt = 0;
for(int i = 0; i < maxn; i++)
pa[i] = i;
while(x != -1)
{
scanf("%d", &y);
x = find(x);
y = find(y);
if(x == y)
cnt++;
else
pa[x] = y;
scanf("%d", &x);
}
printf("%d\n", cnt);
}
return 0;
}