家族

Time Limit: 1 Sec Memory Limit: 256 MB

题目连接

http://www.codevs.cn/problem/1073/

Description

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

Input

第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有 n个人，m个亲戚关系，询问p对亲戚关系。以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有亲戚关系。接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。

Output

P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

Sample Input

6 5 3

1 2

1 5

3 4

5 2

1 3

1 4

2 3

5 6

Sample Output

Yes

HINT

n<=5000,m<=5000,p<=5000

题意

题解：

并查集嘛，然后搞一搞，注意路径压缩就好了

不过我用的递归版本，然而并没有RE，非常开心

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

//const int inf=0x7fffffff;   //无限大

const int inf=0x3f3f3f3f;

/*

inline ll read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int buf[10];

inline void write(int i) {

  int p = 0;if(i == 0) p++;

  else while(i) {buf[p++] = i % 10;i /= 10;}

  for(int j = p-1; j >=0; j--) putchar('0' + buf[j]);

  printf("\n");

}

*/

//**************************************************************************************

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int fa[maxn];

int fi(int x)

{

    if(x!=fa[x])

        fa[x]=fi(fa[x]);

    return fa[x];

}

void un(int x,int y)

{

    int a=fi(x),b=fi(y);

    if(a!=b)

    {

        fa[b]=a;

    }

}

int main()

{

    int n=read(),m=read(),q=read();

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

        fa[i]=i;

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

    {

        int a=read(),b=read();

        un(a,b);

        //cout<<fa[a]<<" "<<fa[b]<<" "<<"123123123"<<endl;

    }

    for(int i=;i<q;i++)

    {

        int a=read(),b=read();

        if(fi(a)==fi(b))

        {

            printf("Yes\n");

        }

        else

            printf("No\n");

    }

}

家族

codevs 1073 家族 并查集

家族