并查集。
~~~
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;
const int N=10005;
const int INF=0x3f3f3f3f;

struct UFS{
int set[N];
int operator {
return set[x];
}
void MAKE_SET(int x){
set[x]=x;
}
int FIND_SET(int x){
if(x!=set[x]) set[x]=FIND_SET(set[x]);
return set[x];
}
void UNION(int x,int y){
x=FIND_SET(x);
y=FIND_SET(y);
if(x!=y) set[x]=y;
}
};

UFS T;
int n,m,p,u,v;
int main(){
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)
T.MAKE_SET(i);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
T.UNION(u,v);
}
for(int i=1;i<=p;i++){
scanf("%d%d",&u,&v);
if(T.FIND_SET(u)==T.FIND_SET(v))
printf("Yes\n");
else printf("No\n");
}
return 0;
}

#include<cstdio>
#include<iostream>
using namespace std;
int bin[1002];
int findx(int x)
{
int r=x;
while(bin[r] !=r)
r=bin[r];
return r;
}
void merge(int x,int y)
{
int fx,fy;
fx = findx(x);
fy = findx(y);
if(fx != fy)
bin[fx] = fy;
}
int main(){
freopen("bin.in","r",stdin);
freopen("bin.out","w",stdout);
int x,y,i,m,n,p;
cin>>n>>m>>p;
{
for(i=1;i<=n;i++)
bin[i] = i;
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
merge(x,y);
}
for(i=1;i<=p;i++){
cin>>x>>y;
if(findx(x)==findx(y))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}

}

裸并查集

#include <iostream>

using namespace std;

const int maxn = 5000 + 5;

int data[maxn];
int tree[maxn];
int height[maxn];

void Build(int n)
{
    for (int i = 0; i < n; i++)
    {
        tree[i] = i;
        height[i] = 0;
    }
}

int Find(int n)
{
    if (n == tree[n])
        return n;
    return tree[n] = Find(tree[n]);
}

void Unite(int a, int b)
{
    a = Find(a);
    b = Find(b);
    if (a == b)
        return ;
    if (height[a] < height[b])
        tree[a] = b;
    else
    {
        tree[b] = a;
        if (height[a] == height[b])
            height[a]++;
    }
}

string Query(int a, int b)
{
    if (Find(a) == Find(b))
        return "Yes";
    else
        return "No";
}

int main()
{
    int n, m, p;
    while(cin >> n >> m >> p)
    {
        Build(n);
        for (int i = 0; i < m; i++)
        {
            int a, b;
            cin >> a >> b;
            Unite(a, b);
        }
        for (int i = 0; i < p; i++)
        {
            int a, b;
            cin >> a >> b;
            cout << Query(a, b) << endl;
        }
    }
    
    return 0;
}

瞎写的递归主函数……其实能用的，还能A
```C++
#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include<iostream>
#include<set>
#include<stdlib.h>
#include<string>
#include<cstring>
using namespace std;

long father[50000] = { 0 };
long found(long node)
{
if (father[node] == node) return node;
father[node] = found(father[node]);
return father[node];
}

void bringcharge(long l, long r)
{
l = found(l);
r = found(r);
if (l != r) father[r] = l;
return;
}
long a[] = { 1, 2, 3, 0 };
long n, m, q;
long *qqq = a;

int main(long *rr)
{
rr = qqq++;
if (*rr == 1){
ios::sync_with_stdio(false);
cin >> n >> m >> q;
for (long i = 1; i <= n; i++)
father[i] = i;
main(qqq);
}
else if (*rr == 2){
for (long i = 1; i <= m; i++)
{
long l, r;
cin >> l >> r;
bringcharge(l, r);
}
main(qqq);
}
else if (*rr == 3)
{
for (long i = 1; i <= q; i++)
{
long l, r;
cin >> l >> r;
if (found(l) != found(r))cout << "No" << endl;
else cout << "Yes" << endl;
}
main(qqq);
}
// system("pause");
else exit(0);
}
```

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int arr[5010];
int find(int a)//查找a的根节点，并返回
{
    if (arr[a] == a) return a;
    else arr[a] = find(arr[a]);
    return arr[a];
}
void initial(int m)
{
    int a, b, t1, t2;
    for (int i = 0; i<m; i++)
    {
        cin >> a >> b;
        t1 = find(a);
        t2 = find(b);
        if (t1 != t2) { arr[b] = t1; arr[t2] = t1; }//用find函数来找a和b的根节点，看他们是否相等，相等就不管，不等就让b的根节点指向a的根节点
    }
}
void check(int p)
{
    int a, b;
    for (int i = 0; i<p; i++)
    {
        cin >> a >> b;
        a = find(a);
        b = find(b);
        if (a==b) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}
int main()
{
    for (int i = 0; i<5008; i++)//初始化，让arr[i]上的值指向自己
        arr[i] = i;
    int n, m, p;
    cin >> n >> m >> p;
    initial(m);
    check(p);
    //system("pause");
    return 0;
}

//并查集水水的过了
#include<cstdio>
int father[5000];

int find_father(int v)
{
if(father[v]==v)
return v;
father[v]=find_father(father[v]);
return father[v];
}

void merge(int p,int q)
{
int i,j;
i=find_father(p);
j=find_father(q);
father[i]=j;
}

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

int main()
{
int n,m,p,i,j;
scanf("%d%d%d",&n,&m,&p);
for(i=1;i<=n;i++)
{
father[i]=i;
}
for(i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
merge(x,y);
}
for(i=1;i<=p;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(judge(x,y))
puts("Yes");
else
puts("No");
}
}

测试数据 #0: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 572 KiB, score = 10
Accepted, time = 0 ms, mem = 572 KiB, score = 100
代码
#include<cstdio>
#include<iostream>
using namespace std;

const int Max = 5000 + 10;

int N, M ,P, A, B, Parent[Max];

inline int getInt() {
int Return = 0;
char Get = getchar();
while(Get >= '0' && Get <= '9') {
Return = Return * 10 + (Get - '0');
Get = getchar();
}
return Return;
}

inline int Find(int theElement) {
int theRoot = theElement;
while (Parent[theRoot] != theRoot)
theRoot = Parent[theRoot];
int parentNode;
int Now = theElement;
while(Now != theRoot) {
parentNode = Parent[Now];
Parent[Now] = theRoot;
Now = Parent[Now];
}
return theRoot;
}

int main() {
N = getInt(); M = getInt(); P = getInt();
for(int i = 1; i <= N; ++i) Parent[i] = i;
for(int i = 1; i <= M; ++i) {
A = getInt(); B = getInt();
A = Find(A); B = Find(B);
if(A != B) Parent[B] = A;
}
for(int i = 1; i <= P; ++i) {
A = getInt(); B = getInt();
if(Find(A) == Find(B)) printf("Yes\n");
else printf("No\n");
}
return 0;
}

垃圾版题解：
c++
#include<stdio.h>
#include<string.h>
int f[5001]={0};
int ff(int a){
if(f[a]==0) return a;else
return f[a]=ff(f[a]);
}
int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int a,b,i=0;i<m;++i){
scanf("%d%d",&a,&b);
int x=ff(a),y=ff(b);
if(x!=y) f[x]=y;
}
for(int a,b,i=0;i<k;++i){
scanf("%d%d",&a,&b);
printf("%s\n",ff(a)==ff(b)?"Yes":"No");
}
}


555，原来输出没换行WA了
#include<iostream>
using namespace std;
int pa[5001];
int findset(int x)
{
return pa[x]!=x?pa[x]=findset(pa[x]):x;
}
int main()
{
int n,m,p;
cin>>n>>m>>p;
for (int i=1;i<=n;i++)
pa[i]=i;
int a,b,x,y;
for (int i=1;i<=m;i++)
{
cin>>a>>b;
x=findset(a);y=findset(b);
if (x!=y)pa[x]=y;
}

for (int i=1;i<=p;i++)
{
cin>>a>>b;
x=findset(a);y=findset(b);
if (x==y)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}

program p1034;
var
father:array[1..6000] of longint;
n,m,p,i,x,y:longint;
function getfather(x:longint):longint;
begin
if father[x]=x then
exit(x)
else begin
father[x]:=getfather(father[x]);
exit(father[x]);
end;
end;
procedure merge(x,y:longint);
var
fa1,fa2:longint;
begin
fa1:=getfather(x);
fa2:=getfather(y);
father[fa1]:=fa2;
end;
function judge(x,y:longint):boolean;
var
fa1,fa2:longint;
begin
fa1:=getfather(x);
fa2:=getfather(y);
if fa1=fa2 then
judge:=true
else judge:=false;
end;
{main}
begin
readln(n,m,p);
for i:=1 to n do
father[i]:=i;
for i:=1 to m do
begin
readln(x,y);
merge(x,y);
end;
for i:=1 to p do
begin
readln(x,y);
if judge(x,y) then
writeln('Yes')
else writeln('No');
end;
end.

#include <cstdio>

using namespace std;

int n=0,m=0,p=0,set[5001];

int root(int n) {
int path[5001],len=0;
while (set[n]!=n) {
path[len++]=n;
n=set[n];
}
for (int i=0;i<len;++i)
set[path[i]]=n;
return n;
}

int main(void) {
scanf("%d %d %d",&n,&m,&p);
for (int i=1;i<=n;++i)
set[i]=i;
for (int i=0;i<m;++i) {
int a=0,b=0;
scanf("%d %d",&a,&b);
set[b]=a;
}
for (int i=0;i<p;++i) {
int a=0,b=0;
scanf("%d %d",&a,&b);
if (root(a)==root(b))
printf("Yes\n");
else
printf("No\n");
}
return 0;
}

QwQ 我好菜

我什么也不知道
var
f:array[0..5009] of longint;
x,y,fx,fy,i,n,m,p:longint;
function find(x:longint):longint;
begin
if f[x]=x then exit(x);
f[x]:=find(f[x]); exit(f[x]);
end;
begin
readln(n,m,p);
for i:=1 to n do f[i]:=i;
for i:=1 to m do
begin
read(x,y);
fx:=find(x);
fy:=find(y);
if fx<>fy then f[fx]:=fy;
end;
for i:=1 to p do
begin
read(x,y);
if find(x)=find(y)
then writeln('Yes') else writeln('No');
end;
end.

注意两根相同的判断
。。。。
#include <stdio.h>
#include <iostream>
using namespace std;
int rt[10010]={0},n,m,q;

int find(int p){
if(rt[p]==0)
return p;
else{
rt[p]=find(rt[p]);
return rt[p];
}
}

int main(){
int i,j,k,x,y;
scanf("%d%d%d",&n,&m,&q);
for(i=1;i<=m;++i){
scanf("%d%d",&x,&y);
j=find(x);
k=find(y);
if(j!=k){
rt[j]=k;
}
}
for(i=1;i<=q;++i){
scanf("%d%d",&x,&y);
if(find(x)==find(y)) printf("Yes\n");
else printf("No\n");
}
}

http://www.cnblogs.com/oierforever/p/4763790.html

AC 35道纪念
弱弱的 并查集AC
编译成功

测试数据 #0: Accepted, time = 14 ms, mem = 556 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 564 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 564 KiB, score = 10
测试数据 #5: Accepted, time = 31 ms, mem = 556 KiB, score = 10
测试数据 #6: Accepted, time = 94 ms, mem = 560 KiB, score = 10
测试数据 #7: Accepted, time = 78 ms, mem = 560 KiB, score = 10
测试数据 #8: Accepted, time = 109 ms, mem = 556 KiB, score = 10
测试数据 #9: Accepted, time = 109 ms, mem = 560 KiB, score = 10
Accepted, time = 465 ms, mem = 564 KiB, score = 100
代码
include <iostream>
include <cstdio>
include <algorithm>
using namespace std;
int i,j,n,m,z,k,l,q,p,s1,s2;
int a[10002];
char f[10002];
int find(int x)
{
if (a[x]==0) return x;
else if (a[a[x]]==0) return a[x];
a[x]=find(a[x]);
return a[x];
}
int main()
{
l=1;
cin>>n>>m>>z;
for (i=1;i<=m;i++)
{
cin>>s1>>s2;
q=find(s1); p=find(s2);
if (q!=p) a[q]=p;
}
for (i=1;i<=z;i++)
{
cin>>s1>>s2;
q=find(s1); p=find(s2);
if (q==p) {f[l]='y'; l++;}
else {f[l]='n';l++;}
}
for (i=1;i<=l-1;i++)
if (f[i]=='y') cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}

裸的并查集
#include <cstdio>
#define maxn 5005
int rep[maxn];
int findRep(int x)
{
return rep[x]==x?x:rep[x]=findRep(rep[x]);
}

int main()
{
int n,m,p;scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++) rep[i]=i;
for(int i=1;i<=m;i++) {
int x,y;scanf("%d%d",&x,&y);
int r1=findRep(x),r2=findRep(y);
rep[r2]=r1;

}
for(int i=1;i<=p;i++) {
int x,y;scanf("%d%d",&x,&y);
//if(rep[x]==rep[y]) printf("Yes\n");
int r1=findRep(x),r2=findRep(y);
if(r1==r2) printf("Yes\n");
else printf("No\n");
}
return 0;
}

记录信息
评测状态 Accepted
题目 P1034 家族
递交时间 2015-07-11 11:55:58
代码语言 C++
评测机 VijosEx
消耗时间 60 ms
消耗内存 4192 KiB
评测时间 2015-07-11 11:56:04
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 4192 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 4192 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 4192 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 4188 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 4188 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 4192 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 4188 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 4192 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 4192 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 4188 KiB, score = 10
Accepted, time = 60 ms, mem = 4192 KiB, score = 100
代码
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int relative[1000000];
int find(int a)
{
if(relative[a]==a)
return a;
else return relative[a]=find(relative[a]);
}
int main()
{
int n,k,q;
scanf("%d%d%d",&n,&k,&q);
for(int i=1;i<=n;i++)
relative[i]=i;

for(int i=1;i<=k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
int rex=find(x);
int rey=find(y);
relative[rex]=rey;
}

for(int i=1;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(find(x)==find(y))
printf("Yes\n");
else
printf("No\n");

}
}

var
a:array[1..5000]of longint;
p,n,m,i,x,y,f1,f2:longint;
function fa(s:longint):longint;
var t,tt:longint;
begin
t:=s;
while t<>a[t] do
t:=a[t];
while s<>a[s] do
begin
tt:=s;
s:=a[s];
a[tt]:=t;
end;
end;
begin
read(n,m,p);
for i:=1 to n do
a[i]:=i;
for i:=1 to m do
begin
read(x,y);
a[y]:=x;
end;
for i:=1 to p do
begin
read(x,y);
f1:=fa(x);
f2:=fa(y);
if f1=f2 then writeln('Yes')
else writeln('No');
end;
end.

#include<cstdio>
using namespace std;

int pre[5050];

int Find(int x)
{
int r=x;
while(r!=pre[r])
r=pre[r];

int i=x,j;
while(pre[i]!=r)
{
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}

void mix(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx!=fy)
{
pre[fy]=fx;
}
}

int main()
{
int n,m,p,i,a,b;
scanf("%d%d%d",&n,&m,&p);

for(i=1;i<=n;i++)
pre[i]=i;
for (i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
if (Find(a)!=Find(b))
mix(a,b);
}

for (i=1;i<=p;i++)
{
scanf("%d%d",&a,&b);
if (Find(a)==Find(b))
printf("Yes\n");
else
printf("No\n");
}
return 0;
}

n,m,p=[int(i)for i in raw_input().split()]

s=[]
for i in range(0,n+1):
s.append([i,1])

def find(a):
while a!=s[a][0]:
s[a][0]=s[s[a][0]][0]
a=s[a][0]
return a

def link(a,b):
ar=find(a)
br=find(b)
if ar!=br:
if s[ar][1]<s[br][1]:
s[ar][0]=br
s[br][1]+=s[ar][1]
else:
s[br][0]=ar
s[ar][1]+=s[br][1]

for i in range(0,m):
x,y=[int(j)for j in raw_input().split()]
link(x,y)

for i in range(0,p):
x,y=[int(j)for j in raw_input().split()]
if find(x)==find(y):
print 'Yes'
else:
print 'No'