http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=789

 

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 const int MAXN=30005; 5 int parent[MAXN]; 6  7 int Find(int x)//finds the subset of the x-th element and 8 { 9     //updates its predecessors for furture efficiency10     return (parent[x] == x) ? x : parent[x] = Find(parent[x]);11 }12 void Union(int x, int y)//units two subsets in to a single subset,13 {                       //called when they should share the same parent14     parent[Find(x)] = Find(y);15 }16 int main()17 {18     int n,m;19     while(cin>>n>>m&&(n||m))20     {21         for (int i = 0; i < n; i++) //the index of an element represents the subset it belongs to,22             parent[i] = i;              //so initially its index23         int k,f,t;24         while(m--)25         {26             cin>>k>>f;27 28             while(--k)29             {30                 scanf("%d",&t);31                 Union(f,t);32             }33         }34         int find0=Find(0);35         cout<