分析:并查集,和1107 social cluster很像,本题要在findFa函数中进行路径压缩,否则有一个测试点会超时,并查集还是要多练,太菜了
#include <iostream>
#include<cstring>
#include<vector>
#include<map>
#include<math.h>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define MAX 999999999
int n,m,k;
int fa[10001];
int bird[10001];
int ans[10001];
int findFa(int x)
{
if(x == fa[x]) return x;
return fa[x] = findFa(fa[x]);
}
void uni(int a,int b)
{
fa[findFa(a)] = findFa(b);
}
int main()
{
cin>>n;
for(int i = 1; i <= 10001;i++)
fa[i] = i;
int num = 0;
for(int i = 1; i <= n ;i++)
{
int k;scanf("%d",&k);
int fro ;
for(int j = 0; j < k ; j++)
{
int x;scanf("%d",&x);
if(j == 0)
fro = x;
else
uni(x,fro);
if(bird[x] == 0) num++;
bird[x] = 1;
}
}
int cnt = 0;
for(int i = 1; i <= 10001;i++)
if(fa[i] == i && bird[i] == 1)
cnt++;
cout<<cnt<<" "<<num<<endl;
cin>>k;
for(int i = 0 ; i < k ;i++)
{
int a,b;cin>>a>>b;
if(findFa(a) == findFa(b))
cout<<"Yes\n";
else
cout<<"No\n";
}
return 0;
}