对于并查集，有个有趣的小故事可以加深对并查集的理解

　　小故事

　　话说江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。这样一来，江湖上就形成了一个一个的群落，通过两两之间的朋友关系串联起来。而不在同一个群落的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？ 我们可以在每个朋友圈内推举出一个比较有名望的人，作为该圈子的代表人物，这样，每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”……两人只要互相对一下自己的队长是不是同一个人，就可以确定敌友关系了。 但是还有问题啊，大侠们只知道自己直接的朋友是谁，很多人压根就不认识队长，要判断自己的队长是谁，只能漫无目的的通过朋友的朋友关系问下去：“你是不是队长？你是不是队长？” 这样一来，队长面子上挂不住了，而且效率太低，还有可能陷入无限循环中。于是队长下令，重新组队。队内所有人实行分等级制度，形成树状结构，我队长就是根节点，下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候，只要一层层向上问，直到最高层，就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通，至于他们是如何连通的，以及每个圈子内部的结构是怎样的，甚至队长是谁，并不重要。所以我们可以放任队长随意重新组队，只要不搞错敌友关系就好了。于是，门派产生了。

　　看过了这个故事，是不是对并查集有了更深的认识。并查集其实本质上就是画圈，将一些有联系的圈起来，而在查询方面也更加迅速。

　　先把模版贴一下

　　模版

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int par[10005];
int Rank[10005];
void init(int n){
    for(int i=0;i<=n;i++){
        par[i]=i;
        Rank[i]=0;
    }
}
int find(int x){
    if(par[x]==x) return x;
    return par[x]=find(par[x]);
}
void join(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return ;
    if(Rank[x]<Rank[y]) par[x]=y;
    else {
        par[y]=x;
        if(Rank[x]==Rank[y]) Rank[x]++;
    }
}
bool same(int x,int y){
    return find(x)==find(y);
}

　　然后在做pta上做题的时候做了两道入门的并查集的题目

L2-024 部落

在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。

输入格式：

输入在第一行给出一个正整数N（≤），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：

K P[1] P[2] ⋯ P[K]

其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过1。

之后一行给出一个非负整数Q（≤10^​4​​），是查询次数。随后Q行，每行给出一对被查询的人的编号。

输出格式：

首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。

输入样例：

4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7

输出样例：

10 2

Y

N

思路

其实就是并查集的应用而已，只不过加了一个区分互不相交，这个就直接算有多少个根就行了

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int par[10005];
int Rank[10005];
void init(int n){
    for(int i=0;i<=n;i++){
        par[i]=i;
        Rank[i]=0;
    }
}
int find(int x){
    if(par[x]==x) return x;
    return par[x]=find(par[x]);
}
void join(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return ;
    if(Rank[x]<Rank[y]) par[x]=y;
    else {
        par[y]=x;
        if(Rank[x]==Rank[y]) Rank[x]++;
    }
}
bool same(int x,int y){
    return find(x)==find(y);
}
int main()
{
    int n,m;
    set<int>num;
    cin>>n;
    init(10000);
    for(int i=0;i<n;i++){
        int k,a,b;
        cin>>k>>a;
        num.insert(a);
        for(int i=1;i<k;i++){
            cin>>b;
            num.insert(b);
            join(a,b);
            a=b;
        }
    }
    cout<<num.size()<<' ';
    set<int> t;
    for(int i=1;i<=10000;i++){
        if(num.count(i)) t.insert(find(i));
    }
    cout<<t.size()<<endl;
    cin>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        if(same(a,b)) cout<<'Y'<<endl;
        else cout<<'N'<<endl;
    }
    return 0;
}

L2-010 排座位

布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。

输入格式：

输入第一行给出3个正整数：N（≤100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：宾客1 宾客2 关系，其中关系为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。

这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

输出格式：

对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出No problem；如果他们之间并不是朋友，但也不敌对，则输出OK；如果他们之间有敌对，然而也有共同的朋友，则输出OK but...；如果他们之间只有敌对关系，则输出No way。

思路

纯粹的并查集，再加个二维数组，表示两两敌对关系。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int par[105];
int Rank[105];
void init(int n){
    for(int i=0;i<=n;i++){
        par[i]=i;
        Rank[i]=0;
    }
}
int find(int x){
    if(par[x]==x) return x;
    return par[x]=find(par[x]);
}
void join(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return ;
    if(Rank[x]<Rank[y]) par[x]=y;
    else {
        par[y]=x;
        if(Rank[x]==Rank[y]) Rank[x]++;
    }
}
bool same(int x,int y){
    return find(x)==find(y);
}
int main()
{
    int n,m,k;
    int num[105][105];
    memset(num,0,sizeof(num));
    cin>>n>>m>>k;
    init(n);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(c==-1) num[a][b]=num[b][a]=c;
        else join(a,b);
    }
    for(int i=0;i<k;i++){
        int a,b;
        cin>>a>>b;
        if(num[a][b]==-1){
            if(same(a,b)) cout<<"OK but..."<<endl;
            else cout<<"No way"<<endl;
        }
        else {
            if(same(a,b)) cout<<"No problem"<<endl;
            else cout<<"OK"<<endl;
        }
    }
    return 0;
}