首页 > 代码库 > UVALIVE 3644 X-Plosives

UVALIVE 3644 X-Plosives

并查集

#include<iostream>#include<cstdio>using namespace std;#define MAXN 100005int p[MAXN],N;int Find(int x) {return x == p[x] ? x : p[x] = Find(p[x]);}int main(){    //freopen("sample.txt","r",stdin);    int u, v;    while (scanf("%d",&u) != EOF)    {        int ans = 0;        if (u == -1) break;        for (int i = 0; i < MAXN; i++) p[i] = i;        scanf("%d",&v);        int x = Find(u), y = Find(v);        if (x != y) p[x] = y;        else ans++;        while (scanf("%d",&u) != EOF)        {            if (u == -1) break;            scanf("%d",&v);            int x = Find(u), y = Find(v);            if (x != y) p[x] = y;            else ans++;        }        printf("%d\n",ans);    }    return 0;}

 

UVALIVE 3644 X-Plosives