首页 > 代码库 > POJ1161(并查集)

POJ1161(并查集)

1、题目链接地址

  http://poj.org/problem?id=1161

2、源代码

#include <iostream>using namespace std;int parent[30001];int suspect[30001]; int find(int x){   if(parent[x] == x)   {      return x;   }   else   {      return parent[x] = find(parent[x]);   }} void Union(int a, int b){   int x = find(a);   int y = find(b);   if(x == y)   {      return;   }   parent[y] = x;   suspect[x] = suspect[x] + suspect[y];} int main(){   int m, n;   int a, b, c;   int x;   int i;   while(cin >> m >> n)   {      if(m == 0 && n == 0)      {          break;      }            for(i = 0; i <= m; i++)      {        parent[i] = i;        suspect[i] = 1;      }            while(n--)      {        cin >> a >> b;        a--;        while(a--)        {           cin >> c ;           if(find(c) != find(b))           {               Union(c, b);           }        }      }       cout << suspect[find(0)] << endl;   }   return 0;}