不想看模板，想直接看题目的请戳下面目录：
目录：
POJ 2236 Wireless Network 【传送门】
POJ 1703 Find them, Catch them 【传送门】
先上模板：
#define MAXN 根据编号需要
int per[MAXN],rank[MAXN]; void init(int n)
{
int i;
for(i=;i<=n;i++)
{
per[i]=i;rank[i]=
} } int find(int x)
{
if(x==per[x])
return x;
return per[x]=find(per[x]);
} void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return;
if(rank[x]>rank[y])
per[y]=x;
else
{
per[x]=y;
if(rank[x]==rank[y])
rank[y]+=;
}
} bool same(int x,int y)
{
return find(x)==find(y);
}
并查集详解请访问：（通俗易懂解释）
https://blog.csdn.net/lesileqin/article/details/96703143
接下来来看几个例子：
HDU 1213 How Many Tables【传送门】
题目大意：有一个人过生日，请到了他的诸多朋友，但是这些朋友之间有的认识，有的不认识。这个人想尽可能的把相互之间认识的人凑到一张桌子上，不认识的人则去另一张桌子。朋友们互相认识的规则是：比如A认识B，B认识C，那么A，B，C就可以凑到一桌子上。现在问：他的朋友们以这样的规则能凑够几桌。
解题思路：运用并查集，把相互认识的人都联合一下，到最后计算数组中有几个per值等于自身的人就可以了。
#include<iostream> using namespace std; int f[]; void init(int n)
{
for(int i=;i<=n;i++)
f[i]=i;
} int find(int a)
{
while(a!=f[a])
{
a=f[a];
}
return a;
} void Combin(int a,int b)
{
int ta,tb;
ta=find(a);
tb=find(b); if(ta!=tb)
f[ta]=tb;
} int answer(int n)
{
int sum=;
for(int i=;i<=n;i++)
if(f[i]==i)
sum++;
return sum;
} int main()
{ int t;
cin >> t;
while(t--)
{
int n,m;
cin >> n >> m;
init(n);
int a,b;
for(int i=;i<m;i++)
cin >> a >> b,Combin(a,b);
cout << answer(n) << endl ;
} return ;
}
HDU 1232 畅通工程 【传送门】
此处略去题目大意……
解题思路：其实这个题目和上一个题异曲同工，就是变换了一下条件，我们假设村子是上题的朋友，那么路就是朋友们之间的关系，那么两堆朋友之间连线，其实只需要一次就可以了，同样，三堆朋友之间要想相互认识，只需要两个关系就可以了，所以我们很容易可以得出朋友们要想都认识，只需要把朋友堆数 - 1 就可以了。
代码只需要将上题的输出结果-1即可 ，不再贴出。
POJ 2236 Wireless Network 【传送门】
题目大意：一片废弃的地方，ACM协会正在进行救援，可是所有电脑的通信设施都被破坏了，被修复好的电脑的信号传输距离只有d米，现在给出所有电脑的坐标，然后给出指令S与O，S后跟两个数字代表两个电脑的编号，询问这两台电脑是否能通信，如果能则输出SUCCESS，否则输出FALL；O后跟一个编号，代表修好一定电脑。
解题思路：此题运用并查集，在修复好一台电脑之后遍历所有修好的电脑，如果两点间距离小于d米，则连通两个点；遇到S的时候只需要判断是否连通即可。
#include<iostream>
#include<cmath>
using namespace std;
#define MAXN 1005 //坐标
struct pos{
int x,y;
int par_id; //父辈id
int rank; //树的高度
}; struct pos par[MAXN]; //记录父亲
bool isok[MAXN]; //是否被修复成功 float Distance(struct pos a,struct pos b)
{
float dis=sqrt(fabs(a.x-b.x)*fabs(a.x-b.x)+fabs(a.y-b.y)*fabs(a.y-b.y));
return dis;
} void init(int n)
{
for(int i=;i<=n;i++)
{
par[i].par_id=i;
par[i].rank=;
isok[i]=false;
}
} //查树根
int find(int x)
{
if(par[x].par_id==x)
return x;
else
return par[x].par_id=find(par[x].par_id);
} //合并
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return;
if(par[x].rank<par[y].rank)
par[x].par_id=y;
else{
par[y].par_id=x;
if(par[x].rank==par[y].rank)
par[x].rank++;
}
} //判断x和y是不是同一个集合
bool same(int x,int y)
{
return find(x)==find(y);
} int main()
{
int N,d;
char c;
cin >> N >> d;
init(N);
for(int i=;i<=N;i++)
{
int x,y;
cin >> x >> y;
par[i].x=x;
par[i].y=y;
} while(cin >> c)
{
int p,q;
if(c=='O')
{
cin >> p;
isok[p]=true;
for(int i=;i<=N;i++)
{
if(isok[i]==true&&i!=p)
{
struct pos a,b;
a.x=par[i].x;
a.y=par[i].y;
a.par_id=par[i].par_id;
b.x=par[p].x;
b.y=par[p].y;
b.par_id=par[p].par_id;
if(Distance(a,b)<=d)
{
// cout << Distance(a,b) << endl;
unite(p,i);
} }
}
}
else if(c=='S')
{
cin >> p >> q;
if(same(p,q))
cout << "SUCCESS\n";
else
cout << "FAIL\n";
}
// for(int i=1;i<=N;i++)
// cout << par[i].par_id << " ";
// cout << endl;
}
return ;
}
POJ 1703 Find them, Catch them 【传送门】
题目大意：有两个帮派，警察现在抓住了N个罪犯，输入字母A或D，后面跟着两个罪犯的编号。如果字符是A，则代表这一次询问：如果不是一个帮派，则输出“In different gangs.”；是一个帮派输出"In the same gang."；否则输出“Not sure yet.”。如果是字符D，那就代表着后面的两个编号不属于一个帮派！
解题思路：需要一个标记数组vis，用来标记两个罪犯(a,b)不属于同一个帮派，如果标记数组两个罪犯都为0则代表不确定是哪个帮派，并且让vis[a]=b,vis[b]=a；如果vis[a]==0&&vis[b]!=0，则让vis[b]=a，并且连通a,vis[b]；如果vis[b]==0&&vis[a]!=0，则让vis[a]=b，并且连通b,vis[a]；最后一种情况是a与b的标记数组都不为0，那么连2019-07-21通a,vis[b]，连通b,vis[a]最后判断即可。
//#include<iostream>
//using namespace std;
#include<stdio.h>
#define MAXN 100010 int per[MAXN],rank[MAXN],vis[MAXN]; void init(int n)
{
int i;
for(i=;i<=n;i++)
{
per[i]=i;rank[i]=;vis[i]=;
} } int find(int x)
{
if(x==per[x])
return x;
return per[x]=find(per[x]);
} void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return;
if(rank[x]>rank[y])
per[y]=x;
else
{
per[x]=y;
if(rank[x]==rank[y])
rank[y]+=;
}
} int Same(int x,int y)
{
if(find(x)==find(y))
return ; } int main()
{
// ios::sync_with_stdio(false);
int t;
scanf("%d",&t);
// cin >> t;
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
// cin >> n >> m;
init(n);
while(m--)
{
int a,b;
char c[];
scanf("%s",c);
//getchar();
scanf("%d%d",&a,&b);
//cin >> c >> a >> b;
//联立
//printf("%c\n",c);
if(c[]=='D')
{
if(vis[a]==&&vis[b]==)
{
vis[a]=b;
vis[b]=a;
}
else if(vis[a]==)
{
vis[a]=b;
unite(a,vis[b]);
}
else if(vis[b]==)
{
vis[b]=a;
unite(b,vis[a]);
}
else{
unite(a,vis[b]);
unite(b,vis[a]);
}
}
else{
if(Same(a,b))
printf("In the same gang.\n");
//cout << "In the same gang.\n";
else if(Same(a,vis[b]))
//cout << "In different gangs.\n";
printf("In different gangs.\n");
else
printf("Not sure yet.\n");
//cout << "Not sure yet.\n";
}
}
} return ;
}