题解 - Vijos

22

首先这是一道显然的并查集模版题。
如果不知道并查集是什么，可以理解为一个个集合，不断合并集合。
看到题解里有用启发式合并的，不过此题显然没什么必要。

#include<bits/stdc++.h>
using namespace std;
const int N=5000;
int fa[N+1];

//寻找父节点，即集合序号
int find(int x)
{
    return fa[x]==x? x:fa[x]=find(fa[x]);
}

int main()
{

int n,m,p;
    cin>>n>>m>>p;
    
    for (int i = 1; i <= n; i++)
    fa[i]=i;
        //初始化每个元素作为一个单独的集合
        
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        fa[find(y)]=find(x);
        //每次合并一下集合
    }
    for(int i=1;i<=p;i++)
    {
        int x,y;
        cin>>x>>y;
        if(find(x)==find(y)) 
        cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        
        //判断两个是否在一个集合
    }

return 0;
}

求赞<
求顶<
谢谢<

3

伊人 LV 8 @ 7 年前

并查集模板题(○’ω’○)（带路径压缩）

#include<iostream>
using namespace std;
int father[5005];
int n,m,p,x,y;
int find(int x)
{
    if(father[x]!=x)father[x]=find(father[x]);
    return father[x];
}
void unionn(int x,int y)
{
    x=find(x);y=find(y);
    father[y]=x;
}
bool judge(int x,int y)
{
    x=find(x);y=find(y);
    if(father[x]==father[y])return true;
    else return false;
}
int main()
{
    cin>>n>>m>>p;
    for(int i=1;i<=n;++i)
    father[i]=i;
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y;
        unionn(x,y);
    }
    for(int i=1;i<=p;++i)
    {
        cin>>x>>y;
        if(judge(x,y)==1)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

1

2023gdsy119 LV 7 @ 1 年前

//437.亲戚 
#include<bits/stdc++.h>
using namespace std;
int n,m,q,uf[1000005];
int find(int x){
    if(uf[x]==x)
        return x;
    return uf[x]=find(uf[x]);
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        uf[i]=i;
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        uf[find(x)]=find(y);
    }
    while(q--){
        int x,y;
        scanf("%d%d",&x,&y);
        printf((find(x)==find(y))?"Yes\n":"No\n");
    }
    return 0;
}

1

November (CLH_W) LV 10 @ 3 年前

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cmath>
 
#define mxn 5000+10
#define loc
 
using namespace std;
 
int n,m,p;
int f[mxn];
 
int fd(int x)
{
    if (f[x]==x) return x;
    f[x]=fd(f[x]);
    return f[x];
}
 
int mrg(int x,int y)
{
    int rx=fd(x),ry=fd(y);
    f[rx]=f[ry];
}
 
int main()
{
    #ifdef loc
   
    #endif
    
    scanf("%d%d%d",&n,&m,&p);
    
    for (int i=1;i<=n;++i) f[i]=i;
    int x,y;
    for (int i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        mrg(x,y);        
    }
    
    for (int i=1;i<=p;++i)
    {
        scanf("%d%d",&x,&y);
        if (fd(x)==fd(y)) printf("Yes\n");
        else printf("No\n");
    }
    
    return 0;
}

1

血色X战魂 LV 8 @ 6 年前

路压+按秩

#include<iostream>
#include<algorithm>
using namespace std;
//呵呵
//大神万岁
//分割线--------------------------------------------------$
//结构定义区
//全局变量区
int t[5001],order[5001];
int n,m,p;
//函数声明区
int getf(int v);
void merge(int a,int b);
void init(int n);
//主函数开始！
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)
    {
        t[i]=i;
        order[i]=1;
    }
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        merge(a,b);
    }
    for(int i=0;i<p;i++)
    {
        int a,b;
        cin>>a>>b;
        if(getf(a)==getf(b)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl; 
    }
    return 0;
} 
//函数实现区
int getf(int v)
{
    if(t[v]==v) return v;
    else
    {
        t[v]=getf(t[v]);
        return t[v];
    }
 } 
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        t[n]=n;
        order[n]=1;
    }
}
void merge(int a,int b)
{
    int t1,t2;
    t1=getf(a);
    t2=getf(b);
    if(t1!=t2){
    if(order[t1]>=order[t2])
    {
        t[t2]=t1;
        order[t1]+=order[t2];
    }
    else
    {
        t[t1]=t2;
        order[t2]+=order[t1];
    } 
    }
}

1

Elucidator LV 7 @ 6 年前

模板题
#include<iostream>
using namespace std;
const int maxn = 1000000;
int n,m,p,f[maxn];
int init(){
for (int i = 1;i<=n;i++)
f[i] = i;
return 0;
}
int ffind(int v){
if (f[v]==v)
return v;
else
{
f[v] = ffind(f[v]);
return f[v];
}
}
void hm(int u,int v){
int t1,t2;
t1 = ffind(u);
t2 = ffind(v);
if (t1!=t2)
{
f[t2] = t1;
}
return;
}
int judge(int u,int v){
int t1,t2;
t1 = ffind(u);
t2 = ffind(v);
if (t1!=t2)
{
return 0;
}
return 1;
}
int main()
{
// freopen("testi.txt","r",stdin);
cin >> n >> m >> p;
init();

for (int i = 1; i<=m; i++){
int x,y;
cin >> x >> y;
hm(x,y);
}

for (int i = 1;i<=p;i++){
int x,y;

cin >> x >> y;

if (judge(x,y))
cout << "Yes" << endl;
else
cout << "No" << endl;

}
return 0;
}

1

清风breeze LV 8 @ 7 年前

#include<cstdio>
int set[10010];
int n, m, p;
int find(int x){
    if(set[x]==x) return x;
    else return set[x]=find(set[x]);
}
int merge(int x, int y){
    int _x=find(x), _y=find(y);
    if(_x!=_y) set[_x]=_y;
}
void solve(){
    int i, x, y;
    scanf("%d%d%d", &n, &m, &p);
    for(i=1; i<=n; i++) set[i]=i;
    for(i=1; i<=m; i++){
        scanf("%d%d", &x, &y);
        merge(x, y);
    }
    for(i=1; i<=p; i++){
        scanf("%d%d", &x, &y);
        if(find(x)==find(y)) printf("Yes\n");
        else printf("No\n");
    }
}
int main(){
    solve();
    return 0;
}

1

yyyz108 LV 8 @ 7 年前

简单的一个并查集，不断合并并查集即可

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,p,x,y,s,t;
int f[5200];
int find(int q)//寻找当前祖先，合并并查集 
{
    return f[q]==q?q:f[q]=find(f[q]);
}
int main()
{
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++) f[i]=i;//初始化 
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        f[find(y)]=find(x);//建立关系 
    }
    for(int i=1;i<=p;i++)//通过find寻找 
    {
        cin>>s>>t;
        if(find(s)==find(t))
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl; 
    }
    return 0;
}

1

PowderHan LV 10 @ 8 年前

/*
再经典不过的并查集了
很简单不想多说
只想提到的是
这个pa数组有很多种初始化
初学可以pa[i]=i
到了后面熟练一点用pa[i]=0来就更方便一些了
*/
#include <iostream>
using namespace std;

int pa[20005];
int n,m;

int Getfather(int x)
{
    return pa[x]==x?x:pa[x]=Getfather(pa[x]);   
}

void init()
{
    for(int i=1;i<=n;i++)
    pa[i]=i;
}

void Union(int x,int y)
{
    pa[Getfather(x)]=Getfather(y);
}

int main()
{
    cin>>n>>m;
    int k;
    cin>>k;
    init();
    
    for(int i=1;i<=m;i++)
    {
        int x1,x2;
        cin>>x1>>x2;
        Union(x1,x2);
    }
    
    for(int i=1;i<=k;i++)
    {
        int y1,y2;
        cin>>y1>>y2;
        if(Getfather(y1)==Getfather(y2))
        cout<<"Yes"<<endl;
        else
        cout<<"No"<<endl;
    }
    return 0;
}

1

larryzhong LV 9 @ 8 年前

简单的并查集（路径压缩 + 按秩合并）。
注：数组起名不能叫 rank。

#include <iostream>
using namespace std;

const int maxn = 5010;
int father[maxn], _rank[maxn];

// 查询树的根
int find(int x) {
    if (father[x] == x)
        return x;
    else
        return father[x] = find(father[x]);
}

// 合并 x 和 y 所属的集合
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (_rank[x] < _rank[y])
        father[x] = y;
    else {
        father[y] = x;
        if (_rank[x] == _rank[y])
            _rank[x]++;
    }
}

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        father[i] = i;
    int x, y;
    while (m--) {
        cin >> x >> y;
        unite(x, y);
    }
    while (q--) {
        cin >> x >> y;
        if (find(x) == find(y))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

0

Callous_Murder (陌.) LV 7 @ 5 年前

并查集板子。
不熟悉并查集可以看看蒟蒻某谷的blog。

那么就是合并和查询的操作。

码风恶臭的code

#include<bits/stdc++.h>
using namespace std;
int n,a[10001],m,t,x,y;
int find(int q) {
    if(a[q]==q) return q;
    a[q]=find(a[q]);
    return a[q];
}
int main() {
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=n;++i) a[i]=i;
    while(m--) scanf("%d%d",&x,&y),a[find(x)]=find(y);
    while(t--) scanf("%d%d",&x,&y),find(x)==find(y)?printf("Yes\n"):printf("No\n");
    return 0;
}

0

Gadfly-Km LV 8 @ 7 年前

*****简单的并查集*****

#include<iostream>
using namespace std;
int f[5005];//数组开大一点 
int find(int z)
{
    if (z!=f[z]) return find(f[z]);
    return f[z];//找爸爸~ 
}
int main()
{
    int n,m,p;
    int x,y;
    scanf("%d%d%d",&n,&m,&p);
    for (int i=1;i<=n;i++) f[i]=i;//初始元素为它本身 
    for (int i=1;i<=m;i++){
        cin>>x>>y;
        //scanf("%d%d",&x,&y);
        int c1=find(x);
        int c2=find(y);
        if (c1!=c2) f[c2]=c1;
    }
    for (int i=1;i<=p;i++){
        cin>>x>>y;
        //scanf("%d%d%d",&x,&y);
        if (find(x)==find(y)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}//day1-xfy

0

施支林 LV 8 @ 7 年前


Var
        n,m,p,i,x,y:longint;
        fa:array[1..5000]of longint;
        
Function find(jd:longint):longint;
Var
        zx,xg:longint;
Begin
        zx:=jd;
        while fa[zx]>0 do zx:=fa[zx];

        while fa[jd]>0 do
        begin
                xg:=fa[jd];
                fa[jd]:=zx;
                jd:=xg;
        end;
        exit(zx);
End;

Procedure union(x,y:longint);
Var
        x1,y1:longint;
Begin
        x1:=find(x);
        y1:=find(y);
        if x1<=y1 then
                fa[y1]:=x1
        else
                fa[x1]:=y1;
End;

Begin
        readln(n,m,p);

        for i:=1 to m do
        begin
                readln(x,y);
                if find(x)<>find(y) then
                        union(x,y);
        end;

        for i:=1 to p do
        begin
                readln(x,y);
                if find(x)=find(y) then
                        writeln('Yes')
                else
                        writeln('No');
        end;
        readln;
End.

0

waveBridge LV 7 @ 8 年前

#include<iostream>
#include<cstdio>
using namespace std;

int pre[5010];

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

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

return r;
}

void mix(int a,int b)
{
int fa=find(a),fb=find(b);
if(fa!=fb)
{
pre[fa]=fb;
}
}

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

for(int i=1;i<=n;i++)
{
pre[i]=i;
}

for(int i=0;i<m;i++)
{
int a,b;
scanf("%d %d",&a,&b);

mix(a,b);
}

for(int i=0;i<p;i++)
{
int a,b;
scanf("%d %d",&a,&b);

if(find(a)==find(b))
{
printf("Yes\n");
}

else
printf("No\n");
}

return 0;
}

0

悲伤の眼泪 LV 8 @ 8 年前

简单的并查集
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int f[10001];
int N, M, P;

int find(int x) {
return f[x]==x ? x : find(f[x]);
}

void hb(int r1, int r2) { f[r2] = r1; }

void init() {
scanf("%d%d%d", &N, &M, &P);
for(int i=1; i<=N; i++) f[i] = i;
for(int i=1; i<=M; i++) {
int x, y;
scanf("%d%d", &x, &y);
int r1 = find(x);
int r2 = find(y);
if(r1 != r2) hb(r1, r2);
}
for(int i=1; i<=P; i++) {
int x, y;
scanf("%d%d", &x, &y);
if(find(x) != find(y)) printf("No\n");
else printf("Yes\n");
}
}

int main() {

init();

return 0;
}

0

风逐天涯 LV 7 @ 8 年前

#主要用数组表示标示符

type int=longint;
var
fam : array[1..10000] of int;
n,m,p,i,a,b : int;
function fa(c :int):int;
begin
if fam[c]=c then exit(c);
fam[c]:=fa(fam[c]);
exit(fam[c]);
end;
procedure isfam(x,y :int);
begin
fam[fa(x)]:=fa(y);
end;

begin
readln(n,m,p);
for i := 1 to n do fam[i] :=i;
for i := 1 to m do
begin
readln(a,b);
isfam(a,b);
end;
for i := 1 to p do
begin
readln(a,b);
if fa(a)=fa(b) then writeln('Yes')
else writeln('No');
end;

end.

0

lambdacat LV 8 @ 8 年前

解的第20个题，纪念一下，这棵裸的并查集
```c++

#include <iostream>
#include <fstream>

#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX_N = 5000 + 50;

int par[MAX_N]; // 父亲
int ranki[MAX_N]; // 树的高度

// 初始化n个元素
void init(int n)
{
for (int i = 0; i < n; i++)
{
par[i] = i;
ranki[i] = 0;
}
}

// 查询树的根
int find(int x)
{
if (par[x] == x)
return x;
else
return par[x] = find(par[x]);
}

// 合并x和y所属的集合
void unite(int x, int y)
{
x = find(x);
y = find(y);
if (x == y) return;

if (ranki[x] < ranki[y]) {
par[x] = y;
}
else {
par[y] = x;
if (ranki[x] == ranki[y])
ranki[x]++;
}
}

// 判断x和y是否属于同一个集合
bool same(int x, int y)
{
return find(x) == find(y);
}

int main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif

int n, m, p; cin >> n >> m >> p;
init(n);

int a, b;
for (int i = 0; i < m; ++i) {
cin >> a >> b;
unite(a, b);
}
for (int i = 0; i < p; ++i) {
cin >> a >> b;
cout << (same(a, b) ? "Yes" : "No") << endl;
}

return 0;
}

0

冲啊小笼包 LV 9 @ 8 年前

pascal 和 C++并查集

###pascal code
program ex;
var fa:array[1..5000] of longint;
i,j,n,m,p,k1,k2:longint;
ans:string;
function father(x:longint):longint;
begin
if fa[x]=x then exit(x);
fa[x]:=father(fa[x]); exit(fa[x]);
end;

procedure add(a,b:longint);
var f1,f2:longint;
begin
f1:=father(a); f2:=father(b); fa[f2]:=f1;
end;

function search(a1,a2:longint):string;
begin
if father(a1)=father(a2) then
exit('Yes')
else
exit('No');
end;

begin //main
read(n,m,p);
for i:=1 to n do fa[i]:=i;

for i:=1 to m do begin
read(k1,k2); add(k1,k2);
end;

for i:=1 to p do begin
read(k1,k2); ans:=search(k1,k2); writeln(ans);
end;

end.

C++ code

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <iostream>
#include <ctype.h>
#include <set>
#define maxn 1000000
using namespace std;

int fa[5100],i,m,p,n,a,b;

int getfather(int x){
if(fa[x]==x){return x;}
fa[x]=getfather(fa[x]);
return fa[x];
}

void add(int x,int y){
x=getfather(x); y=getfather(y); fa[y]=x;
}

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

return 0;
}

0

Deny_小田 LV 8 @ 8 年前

并查集水题
#include <cstdio>

const int size = 6005;
int n,m,p,f[size];

int getfather(int x){
if(f[x] == x) return f[x];
else return f[x] = getfather(f[x]);
}

void Union(int x, int y){
int fx = getfather(x);
int fy = getfather(y);

if( fx != fy ) f[fy] = fx;
}

int main(int argc, char const *argv[]){
scanf("%d %d %d",&n,&m,&p);
for(int i = 1; i <= n; i++) f[i] = i;

for(int i = 1; i <= m; i++){
int x,y;
scanf("%d %d",&x,&y);
Union(x, y);
}

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

return 0;
}

0

水性不好 LV 8 @ 8 年前

正宗大水题并查集经典模板
```#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

int i,j,k,n,m,q,x,y;
int a[100001];

inline int findroot(int t){
int path[10001],k=0,fr,root=t;
while (a[root]!=root){
path[++k]=root;
root=a[root];
}
fr=root;
for (int i=1;i<=k;i++) a[path[i]]=root;
return fr;
}

int main(){
scanf("%d%d%d",&n,&m,&q);
for (i=1;i<=n;i++) a[i]=i;
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
int r1=findroot(x);
int r2=findroot(y);
if (r1!=r2) a[r2]=r1;
}
for (i=1;i<=q;i++){
scanf("%d%d",&x,&y);
if (findroot(x)==findroot(y)) printf("Yes\n");
else printf("No\n");
}
}```

题解

283 条题解

end.

C++ code

家族

信息

状态

开发

支持

题解

283 条题解

end.

C++ code

家族

信息

状态

开发

支持

还没有账户？

登录