- 并查集详解（第二节）

以下是并查集思路详解：

　　一：概念　　　

　　　　并查集处理的是“集合"之间的关系。当给出两个元素的一个无序数对(a,b)时,需要快速“合并”a和b分别所在的集合,这期间需要反复“查找”某元素所在的集合。“并”,“查”,“集”三个字由此而来。

　　　　并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。

　　　　常常在使用中以森林来表示。

　　　　集就是让每个元素构成一个单元素的集合，也就是按一定顺序将属于同一组的元素所在的集合合并。

　　　　在一些有N个元素的集合应用问题中，通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。

　　　　这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高。所以，我们在此引入了并查集；

　　二：初始化

　　　　并查集使用时有一个初始化;数组fa[i]记录了点i的父亲(掌门)是谁；

　　　　所以，我们可以理解成一开始时门派公司还没发展起来，每个人单打独斗，自己是自己的掌门(父亲);

代码：

for(int i=1;i<=n;i++)
    fa[i]=i;

　　三：查找

　　　　用一个judge函数查找自己和对方是否为同一个门派(公司，家族)的人，即他们的掌门(祖宗)是否为同一个人；

代码：

bool judge(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)    return true;
    else return false;
}

　　四：合并

　　　　经过查找后如果两元素不在同一集合，那么用一个函数unionn合并两元素所在集合；

代码：

void unionn(int x,int y)
{
    x=find(x);
    y=find(y);
    fa[y]=x;
}

　　五：寻找根节点（路径压缩）

代码：

int find(int x)
{
    if(fa[x]!=x)    fa[x]=find(fa[x]);    
    //如果该元素还有上级就继续找；最后该元素的上司会直接被置为门派掌门（公司CEO）; 
    return fa[x]; 
}

　六:例题

2832 6个朋友

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题解

题目描述 Description

　　　　　有这么一种说法：认识6个人，你就认识全世界的人。

　　Aiden现在有一张关系图，上面记载了N个人之间相互认识的情况。Aiden想知道，他能否只认识6个人就能间接认识这N个人呢？

输入描述 Input Description

　　第一行，两个数N，M，表示有N个人，M对认识关系。

　　接下来的M行，每行两个数ai，bi，表示ai与bi相互认识。

　　不保证认识关系不出现重复，保证ai≠bi。

　　N个人的编号为1...N。

输出描述 Output Description

　　若只认识6个人就能间接认识这N个人，则输出“^_^”。

　　若不行，则第一行输出“T_T”，第二行输出认识6个人最多能间接认识的人的个数。

　　输出不包括引号。

样例输入 Sample Input

　　6 7

　　1 2

　　1 3

　　2 4

　　3 5

　　4 6

　　5 6

　　3 2

样例输出 Sample Output

　　^_^

数据范围及提示 Data Size & Hint

　　对于30%的数据，保证0＜n≤1000。

　　对于50%的数据，保证0＜n≤5000。

　　对于100%的数据，保证0＜n≤10000，m≤10*n。

思路：裸并查集

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,a[1000000],b[1000000],fa[1000000],v[1000000],sum,ans;
//注意数组大小，n<=100000,开100001的数组不行；此题略坑； 
int find(int x)
{
    if(fa[x]!=x)
        return find(fa[x]);
    else 
        return x;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)    
        fa[i]=i;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
        fa[find(b[i])]=find(a[i]);//b[i]的掌门变成a[i]的掌门； 
    }
    for(int i=1;i<=n;i++)
        fa[i]=find(i);
    for(int i=1;i<=n;i++)
        v[fa[i]]++; 
    for(int i=1;i<=n;i++){
        if(v[i]>0)
            sum++;    
    }
    if(sum<=6)
        cout<<"^_^";
    else
    {
        sort(v+1,v+1+n);
        for(int i=n;i>=n-5;i--)
            ans+=v[i];    
        cout<<"T_T"<<endl;
        cout<<ans;
    }
}