/*Model One*/ //364K 47MS[poj上递归略快一些~] #include<iostream> #include<cstring> using namespace std; const int MAXSIZE = 30005; int parent[MAXSIZE];//根节点储存-num(该树节点数),子节点储存父节点 int Find(int x) {//递归的路径压缩 if(parent[x]>=0) { parent[x] = Find(parent[x]); return parent[x]; } else return x; } void Union(int root1, int root2) { int x = Find(root1),y = Find(root2); if(x==y) return; if(parent[x]<parent[y]) { parent[x] += parent[y]; parent[y] = x; } else{//启发式合并 parent[y] += parent[x]; parent[x] = y; } } void Init(void) { memset(parent,-1,sizeof(parent)); } /*Model Two*/ //364K 63MS #include<iostream> #include<cstring> using namespace std; const int MAXSIZE = 30005; int pre[MAXSIZE];//根节点i,pre[i]=-num,其中num是该树的节点数目 //非根节点j,pre[j]=k,其中k是j的父节点 int Find(int x) {//非递归的路径压缩 int p = x; while(pre[p]>0) p = pre[p];//找到x的根节点p while(x!=p){ int tmp = pre[x];//暂存x的父节点 pre[x] = p;//将x的父节点设为根 x = tmp;//沿路径向上压缩 } return x;//退出时x==p,为根 } void Union(int root1,int root2) { int a = Find(root1), b = Find(root2); if(a==b) return; //加权规则合并 if(pre[a]<pre[b])//a的节点数目大于b { pre[a] += pre[b];//将b并为a的子树 pre[b] = a;//b已是中间节点,使其父节点为a即可 } else { pre[b] += pre[a]; pre[a] = b; } } void Init(void) { memset(pre,-1,sizeof(pre)); } int main() { int n,m; while(cin>>n>>m&&(m+n)) { if(m==0) { cout<<"1"<<endl; continue; } Init(); int sum,x,y; for(int j=0;j<m;j++) { cin>>sum>>x; for(int i=1;i<sum;i++) { cin>>y; Union(x,y); } } /*Model One*/ //cout<<-parent[Find(0)]<<endl; /*Model Two*/ cout<<-pre[Find(0)]<<endl; } return 0; }