/ Vijos / 题库 / 家族 /

题解

281 条题解

  • 20
    @ 2017-06-24 19:02:29

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

    #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
    @ 2017-10-31 20:36:34

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

    #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
    @ 2019-03-09 20:43:55

    路压+按秩

    #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
    @ 2018-07-18 09:31:16

    模板题
    #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
    @ 2017-12-13 14:20:28
    #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
    @ 2017-11-09 11:30:28

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

    #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
    @ 2017-05-07 13:02:08
    /*
    再经典不过的并查集了
    很简单不想多说
    只想提到的是
    这个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
    @ 2017-04-25 13:14:43

    简单的并查集(路径压缩 + 按秩合并)。
    注:数组起名不能叫 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
    @ 2020-06-22 19:32:35

    并查集板子。
    不熟悉并查集可以看看蒟蒻某谷的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
    @ 2017-12-04 22:44:58

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

    #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
    @ 2017-11-26 16:27:37
    
    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
    @ 2017-06-02 16:11:57

    #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
    @ 2017-04-02 09:28:43

    简单的并查集
    #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
    @ 2016-11-15 21:19:46

    #主要用数组表示标示符

    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
    @ 2016-11-10 14:29:18

    解的第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
    @ 2016-09-06 21:52:58

    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
    @ 2016-09-04 18:36:17

    并查集水题
    #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
    @ 2016-08-18 17:15:50

    正宗大水题 并查集经典模板
    ```#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");
    }
    }```

  • 0
    @ 2016-08-06 19:38:40
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    typedef long long lg;
    #define min(a,b) (a>b?b:a)
    #define max(a,b) (a>b?a:b)
    #define MAXX 200011
    //#define OPEN 
    
    lg n,m,k,s,a,b,f[MAXX];
    
    lg read()
    {
        lg res=0;
        char c;
        while((c=getchar())>='0' && c<='9')
          res=res*10+c-'0';
        return res;
    }
    
    void out(lg n)
    {
        if(n>9) out(n/10);
        putchar(n%10+'0');
    }
    
    lg find(int n)
    {
        return f[n]==n ? n:(f[n]=find(f[n]));
    }
    
    int main(int argc, char** argv)
    {
    #ifdef OPEN
       freopen("data.in","r",stdin);
    #endif
        n=read();
        m=read();
        s=read();
        for(int i=1;i<=n;i++)
            f[i]=i;
        for(int i=1;i<=m;i++)
        {
            a=find(read());
            b=find(read());
            if(a!=b)
                f[a]=b;
        }
        for(int i=1;i<=s;i++)
        {
            a=find(read());
            b=find(read());
            if(a!=b)
                puts("No");
            else
                puts("Yes");
        }
        return 0;
    }
    
  • 0
    @ 2016-07-18 13:28:17

    并查集。
    ~~~
    #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;
    }

信息

ID
1034
难度
4
分类
数据结构 | 并查集 点击显示
标签
(无)
递交数
9284
已通过
3804
通过率
41%
被复制
7
上传者