题意
给出n和m,表示有n个人(注意,n个人的编号是从0 ~ n-1,初始化的时候别弄错了),接下去给出m行,每行第一个数字为k,表示该行接下去有k个数,这些数中,
如果某一个数为0,说明为可疑人,他所在那一排的人也会变成可疑人,那一排的数在其他的行数中存在的话,那一排也变成了可疑人。
最后让我们输出可疑人的人数。
思路
把每个可疑人先用book标记一下,每个人和他所在的那一排人进行merge操作,最后遍历的时候和编号为0的人一起判断是否存在公共祖先即可。
AC代码
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<list>
#include<stdlib.h>
#include<stack>
#include<stdio.h>
#include<queue>
using namespace std;
typedef long long ll;
#define sc(T) scanf("%d",&T)
#define scc(x,y) scanf("%d %d",&x,&y)
#define pr(T) printf("%d
",T)
#define f(a,b,c) for (int a=b;a<c;a++)
#define ff(a,b,c) for (int a=b;a>c;a--)
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define eps 1e-9
#define PI acos(-1)
const int N=30020;
int f[N],a[N];
bool book[N];
int getf(int x)
{
if(f[x]==x)
return x;
return f[x]=getf(f[x]);
}
void merge(int x,int y)
{
int t1=getf(x),t2=getf(y);
f[t2]=t1;
}
int main()
{
int n,m;
while(~scc(n,m))
{
if(n==0&&m==0)
break;
if(m==0)
{
cout<<1<<endl;
continue;
}
f(i,0,n) // 记得初始化!!并且看清i从0还是从1开始!!
f[i]=i;
mem(book,0);
f(ii,0,m)
{
int k;
sc(k);
//0 是可疑者 输出可疑人数
for(int i=1; i<=k; i++)
{
sc(a[i]);
book[a[i]]=1; // 相当于把存在的编号全部列出来 可以说是去重
}
for(int i=2; i<=k; i++)
merge(a[i-1],a[i]);
}
book[0]=1;
int w=0,t1=getf(0);
f(i,0,n)
{
if(book[i]) //存在这个编号的人
{
int t2=getf(i);
if(t1==t2)
w++;
}
}
cout<<w<<endl;
}
return 0;
}