codevs 1073 家族并查集

家族

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("
");
}
*/
//**************************************************************************************
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 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=1;i<=n;i++)
        fa[i]=i;
    for(int i=0;i<m;i++)
    {
        int a=read(),b=read();
        un(a,b);
        //cout<<fa[a]<<" "<<fa[b]<<" "<<"123123123"<<endl;
    }
    for(int i=0;i<q;i++)
    {
        int a=read(),b=read();
        if(fi(a)==fi(b))
        {
            printf("Yes
");
        }
        else
            printf("No
");
    }
}

codevs 1073 家族 并查集

家族