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

LA 3644 X-Plosives

最简单的并查集

多做做水题,加深一下理解

 

 1 //#define LOCAL 2 #include <cstdio> 3  4 const int maxn = 100000 + 10; 5 int parent[maxn]; 6  7 int GetParent(int a) { return parent[a] == a ? a : parent[a] = GetParent(parent[a]); } 8  9 int main(void)10 {11     #ifdef LOCAL12         freopen("3644in.txt", "r", stdin);13     #endif14 15     int x, y;16     while(scanf("%d", &x) == 1)17     {18         for(int i = 0; i < maxn; ++i)    parent[i] = i;19         int cnt = 0;20         while(~x)21         {22             scanf("%d", &y);23             x = GetParent(x); y = GetParent(y);24             if(x == y)    ++cnt;25             else        parent[x] = y;26             scanf("%d", &x);27         }28         printf("%d\n", cnt);29     }30     return 0;31 }
代码君

 

LA 3644 X-Plosives