病毒感染者

测试数据：

100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5 
1 0
0 0

样例输出：4  1  1

分析：  最基础的只需要解决查询问题

//并查集
#include<iostream>
using namespace std;
int m,n,k;
int parent[30010];
void ufs_creat(int n){
    for(int i=0;i<n;i++) parent[i]=-1;
}
int find(int x){
    int s;
    for(s=x;parent[s]>=0;s=parent[s]);
    return s;
}

void ufs_union(int R1,int R2){
    int r1=find(R1),r2=find(R2);
    int tmp=parent[r1]+parent[r2];
    if(parent[r1]>parent[r2]){//说明r2的孩子比r1多，r1接替r2的位置， 
        parent[r1]=r2;
        parent[r2]=tmp; 
    } else{//r2接替r1的位置 
        parent[r2]=r1;
        parent[r1]=tmp; 
    } 
} 
int ufs_size(int x){
    int t=find(x);
    return -parent[t];
}
int main()
{
    while(cin>>n>>m&&n>0){
        ufs_creat(n);
        while(m--){
            int x,y;
            int rx,ry;
            cin>>k;
            k--;
            cin>>x;
            rx=find(x);
//            cout<<"x"<<x<<endl;
            while(k--){
                cin>>y;
                ry=find(y);
                ufs_union(rx,ry);
            }
        }
        cout<<"hello"<<endl;
        cout<<ufs_size(0)<<endl;
    }
} 

 难点就是树的合并，只能树根为负其他的parent[0...n-1] 必须非负

void ufs_union(int R1,int R2){
    int r1=find(R1),r2=find(R2);
    int tmp=parent[r1]+parent[r2];
    if(parent[r1]>parent[r2]){//
        parent[r1]=r2;//!!!!!!!!!!
        parent[r2]=tmp; 
    } else{//r2接替r1的位置 
        parent[r2]=r1;//!!!!!!!!!!
        parent[r1]=tmp; 
    } 
}