SOJ4480 Easy Problem IV （并查集）

Time Limit: 3000 MS    Memory Limit: 131072 K

Description


据说 你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。

现在有n个互不认识的人

对于这一群人 我们要实现两个操作

1.介绍两个人互相之间认识，由于这n个人都非常热情好客 他们会介绍所有自己认识的人给对方 也会介绍给所有对方认识的人

  也就是说 若 A 和 B 认识 ，C 和 D 认识，若我们介绍A和C认识 那么B和D也会互相认识

2.询问 某两个人 是否认识对方

Input


为多组数据

第一行为一个数 代表有多少组数据

对于每一组数据

第一行有两个数n m 分别代表有多少个人 和 多少个操作

接下来m行

对于每一行的第一个数 为1 或 2 代表当前操作是哪一类操作

若为操作1 则输入两个人a b 对这两个人执行操作1

若为操作2 则输入两个人a b 询问这两个人是否认识

(1<=n,m<=10000)

Output


对于每一个操作二

若认识 输出Yes

否则输出No

Sample Input

Sample Output


Yes

Yes

No

思路：本题是并查集的模板题，并查集可以用来判断所属团体，或者分析条件冲突（典型的如食物链问题，真假话判断问题），具体的大家可以上网百度。

AC代码：

#include <stdio.h>

#include <iostream>

using namespace std;

const int maxn=;

int par[maxn],_rank[maxn];

void init(int n){

    for(int i=;i<=n;i++){

        par[i]=i;

        _rank[i]=;

    }

}

int find(int x){

    if(par[x]==x){

        return x;

    }else{

        return par[x]=find(par[x]);

    }

}

void unite(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 T;

    scanf("%d",&T);

    while(T--){

        int n,m;

        scanf("%d %d",&n,&m);

        init(n);

        int a,b,c;

        for(int i=;i<m;i++){

            cin>>a>>b>>c;

            if(a==){

                unite(b,c);

            }else{

                if(same(b,c))printf("Yes\n");

                else printf("No\n");

            }

        }

    }

    return ;

}

巴特西

SOJ4480 Easy Problem IV （并查集）

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章