并查集--(初学,入门)

并查集：这里说下我的理解；拿POJ 1611The Suspects 来讲把；有很多部门，有个人得病了，那么跟他一个部门的人也会得病，得病的人所参加的部门的人也会得病，问最后得病的人是多少；这类的就是要用并查集并就是把相关联的部门并在一起，查就是查找某人得病所产生的导致多少人得病的结果；

对于这道题，原理很简单，细节很重要，就是如何并，如何建树

有两种方式，先讲第一种：

一个节点，有儿子，允许儿子还有子节点；这样建实现简单，但是突然一个节点要找祖宗的话要从后面往上找，如果是一条n的单链那就是o(n)的时间，

AC实现代码：

//532K	79MS
#include<iostream>
using namespace std;
const int MAXN = 30001; /*结点数目上线*/
int pa[MAXN];    /*pa[x]表示x的父节点*/
int son[MAXN];  /*表示儿子的个数*/
void make_set(int x)
{/*创建一个单元集*/
    pa[x] = x;//父亲是本身
    son[x]=1; //儿子也是本身
}
int find_set(int x)
{/*带路径压缩的查找   直到找到祖宗*/
	
    if(x != pa[x])
        pa[x] = find_set(pa[x]);
    return pa[x];
}
/*按秩合并x，y所在的集合*/
void union_set(int x, int y)
{
	int root1,root2;
    root1 = find_set(x);
    root2 = find_set(y);
    if(root1!=root2) //如果分属不同集合，直接并在一起，对于这题这里没有进行优化，
		//即让子代少的并给子代多的这样子代数就比较恒定 不过这题没有这样处理也没事因为没必要- -
    {
		pa[root1]=root2;
		son[root2]+=son[root1];
    }
}
int main()
{
    int n, m, num;  //学生数，部门数，部门的人数
    int i;
    while(cin>>n>>m)
    {
		if(n==0&&m==0)break;
		if(m==0){cout<<1<<endl;continue;}//特殊处理
		for(i = 0; i < n; i++)
			make_set(i);
        for(int i = 1; i <= m; ++i)
        {
            cin>>num;
            int *stu = new int[num];
            for(int j = 0; j < num; ++j)
            {
                cin>>stu[j];
                if(j != 0)
					union_set(stu[j - 1], stu[j]);
            }
            delete(stu);
        }
        cout<<son[find_set(0)]<<endl;  //找到0同学的祖宗 并得到其子孙数
    }
    return 0;
}

解法2：让合并区间时让子代少的往多的并，而且在建部门的树的时候，比如建第一个部门的时候，建一个根节点，然后全部是儿子，而不是建链条！

AC代码：

//488K	15MS
#include <iostream>
using namespace std;

const int MAXN = 30001; /*结点数目上线*/
int pa[MAXN];    /*pa[x]表示x的父节点*/
int rank[MAXN];    /*rank[x]是x的高度的一个上界*/
int son[MAXN];/*son[]存储该集合中元素个数，并在集合合并时更新son[]即可*/

void make_set(int x)
{/*创建一个单元集*/
    pa[x] = x;
    rank[x] = 0;
    son[x] = 1;
}

int find_set(int x)
{
    if(x != pa[x]) 
        pa[x] = find_set(pa[x]);
    return pa[x];
}

/*按秩合并x，y所在的集合*/
void union_set(int x, int y)
{
	int root1,root2;
    root1 = find_set(x);
    root2 = find_set(y);
    if(root1 == root2)return ;
    if(rank[root1] > rank[root2])/*让rank比较高的作为父结点*/
    {
        pa[root2] = root1;
        son[root1] += son[root2];
    }
    else 
    {
        pa[root1] = root2;
        if(rank[root1] == rank[root2])
            rank[root1]++;//写rank[root2]++也没影响
        son[root2] += son[root1];
    }
}

int main()
{
    int n, m, num;  //学生数，部门数，部门的人数
    int i;
    while(cin>>n>>m)
    {
    if(n==0&&m==0)break;
    if(m==0){cout<<1<<endl;continue;}//特殊处理
    	for(i = 0; i < n; i++)
    	make_set(i);
        for(int i = 1; i <= m; ++i)
        {
            cin>>num;
            int x,y;
			cin>>x;   //比前一种做法省空间
            for(int j = 1; j < num; ++j)
            {
                cin>>y;
                union_set(x, y);
				y=x;
            }        
        }
        cout<<son[find_set(0)]<<endl;  //找到0同学的祖宗 并得到其子孙数
    }
    return 0;
}

today lazy . tomorrow die .