学习并查集做的第一道题 基本上就是套用模版的
#include < iostream > #include < stdio.h > using namespace std; int n,m; int father[ 30001 ],num[ 30001 ]; /**//* 初始化数组 */ void makeset( int x){ for ( int i = 0 ;i < x;i ++ ) { father[i] = i; num[i] = 1 ; }} int findset( int x) // 查 { if (x != father[x]) { father[x] = findset(father[x]); } // 回溯 return father[x];} void Union( int a, int b) // 并 { int x = findset(a); int y = findset(b); if (x == y) { return ; } if (num[x] >= num[y]) { father[y] = x; num[x] += num[y]; } else { father[x] = y; num[y] += num[x]; } } int main(){ while (scanf( " %d %d " , & n, & m) != EOF && n != 0 ) { makeset(n); for ( int i = 0 ;i < m;i ++ ) { int l,first,b; scanf( " %d %d " , & l, & first); for ( int j = 1 ;j < l;j ++ ) { scanf( " %d " , & b); Union(first,b); } } printf( " %d\n " ,num[findset( 0 )]); // 输出0的祖宗节点的秩 } return 0 ;}转载于:https://www.cnblogs.com/cyiner/archive/2011/05/16/2048227.html
