总阅读量次

在《算法基础》书中，并查集又被称为不相交集结构：假设有1到N个对象，希望将这些对象分成不相交的集合，在任意给定时间里，每个对象都恰好在一个集合里。对于每个集合，选择一个成员作为集合的标签。例如决定用最小的对象作为标签，可以用“集合2”来表示集合{2,5,7,10}。 抽象结束。

作为一个受益者，我强烈建议先看这篇　超有爱的并查集~ 。　虽不能说是后无来者，但绝对是前无古人，能将知识讲得如此活泼有趣，清晰透彻。望洋兴叹，心向往之。所以在这里只谈一些总结。
先看题，原题链接

---

当芸芸众生忙着在朋友圈中发照片的时候，
总有一些人因为太帅而没有朋友。  
本题就要求你找出那些帅到没有朋友的人。  
输入格式：  
输入第一行给出一个正整数N（≤100），是已知朋友圈的个数；  
随后N行，每行首先给出一个正整数K（≤1000）,  
为朋友圈中的人数，  
然后列出一个朋友圈内的所有人——为方便起见，  
每人对应一个ID号，为5位数字  
（从00000到99999），ID间以空格分隔；  
之后给出一个正整数M（≤10000），为待查询的人数；  
随后一行中列出M个待查询的ID，以空格分隔。  
注意：没有朋友的人可以是根本没安装“朋友圈”，  
也可以是只有自己一个人在朋友圈的人。  
虽然有个别自恋狂会自己把自己反复加进朋友圈，  
但题目保证所有K超过1的朋友圈里都至少有2个不同的人。    

输出格式：  
按输入的顺序输出那些帅到没朋友的人。ID间用1个空格分隔，  
行的首尾不得有多余空格。如果没有人太帅，  
则输出No one is handsome。  
注意：同一个人可以被查询多次，但只输出一次。  

输入样例1：  
3  
3 11111 22222 55555  
2 33333 44444  
4 55555 66666 99999 77777  
8  
55555 44444 10000 88888 22222 11111 23333 88888  

输出样例1：  
10000 88888 23333  

输入样例2：  
3  
3 11111 22222 55555  
2 33333 44444  
4 55555 66666 99999 77777  
4  
55555 44444 22222 11111    

输出样例2：  
No one is handsome

---

这一题考虑用并查集做，现在考虑算法，可以将列举的每一个朋友圈的第一个人作为标签，并将这些标签加入set集合,以便于进行查询。另外再开一个数组为每一个ID置0，默认为未访问标记，查询过的标记置1,如是往复，直到查询结束，因为此题有大量查询语句，所以路径压缩是必须的。且这道题有一个细节：虽然ID号为5位数，但是输入与输出不处理的话，就不满足为5位数，例如00000，存入int型变量输出就会成为0（1位数），所以要固定占位5位，不足5位用0补足。下面是代码：

#include<bits/stdc++.h>
using namespace std;
int pre[100003];
int visit[100003] = {0};
set<int> p;
int finder(int x)
{
    int r = x;
    while(pre[r] != r)
        r = pre[r];
    int y = x,z;
    while(pre[y]!= r){  // 路径压缩
        z = pre[y];
        pre[y] = r;
        y = z;
    }
    return r;
}
void join(int x, int y)
{
    int fx = finder(x);
    int fy = finder(y);
    if(fx != fy)  pre[fx] = fy;
}
int main()
{
    ios::sync_with_stdio(false);
    // 初始化前导节点
    for(int i = 0;i<100003;i++)
        pre[i] = i;
    // 数据
    int n,m,k,id,rt;
    bool flag = true;
    cin>>n;
    while(n--){
        cin>>m>>rt;          //指定根节点
        for(int i = 1;i<m;i++){
            cin>>id;
            join(rt,id);    // 连接该id与根节点。
        }
        if(m != 1)
            p.insert(finder(pre[rt]));// 保存根节点
    }
    cin>>k;
    for(int i = 0;i<k;i++){
        cin>>id;
        if(!visit[id]){
            visit[id] = 1;
            int res = finder(pre[id]);
            auto sig = p.find(res);
            if(sig == p.end()) {    // 没有在某个朋友圈里
                if(!flag) cout<<' ';
                cout<<setw(5)<<setfill('0')<<id;
                flag = 0;
            }
        }
    }
    if(flag) cout<<"No one is handsome"<<'\n';
    else cout<<'\n';
    return 0;
}

对于并查集，

• 需要对根节点操作时，可以在录入数据时，指定某个点为为根节点，并将该节点加入set(红黑树)中，以备查找。
• 当题目存在大量节点查询时，此时路径压缩算法能起到很大的作用，而题目并没有大量查询时，路径压缩算法作用则不明显，反而会有额外时间开销。