我擦,题目描述的太。。。
思路:用一个并查集来维护图的连通分量集合,每次得到一个简单化合物(x,y)时检查x和y是否在同一个集合中。如果是,则拒绝,反之则接受。
#include <stdio.h> const int maxn = 100000 + 10; int pa[maxn]; int find(int x){return pa[x] != x ? pa[x] = find(pa[x]) : x;} int main() { int x, y; while(scanf("%d", &x) == 1){ for (int i=0; i<=maxn; i++) pa[i] = i; int refusals = 0; while(x != -1){ scanf("%d", &y); x = find(x); y = find(y); if (x == y) ++refusals;//如果 x和y代表同一个集合,则拒绝 else pa[x] = y; scanf("%d", &x); } printf("%d\n", refusals); } return 0; }