「vijos1022」Victoria的舞会2

2013年12月31日3,8195

描述

Victoria是一位颇有成就的艺术家，他因油画作品《我爱北京天安门》闻名于世界。现在，他为了报答帮助他的同行们，准备开一个舞会。

Victoria准备邀请n个已经确定的人，可是问题来了：
这n个人每一个人都有一个小花名册，名册里面写着他所愿意交流的人的名字。比如说在A的人名单里写了B，那么表示A愿意与B交流；但是B的名单里不见的有A，也就是说B不见的想与A交流。但是如果A愿意与B交流，B愿意与C交流，那么A一定愿意与C交流。也就是说交流有传递性。

Victoria觉得需要将这n个人分为m组，要求每一组的任何一人都愿意与组内其他人交流。并求出一种方案以确定m的最小值是多少。

注意：自己的名单里面不会有自己的名字。

格式

输入格式

第一行一个数n。接下来n行，每i+1行表示编号为i的人的小花名册名单，名单以0结束。1<=n<=200。

输出格式

一个数，m。

样例1

样例输入1[复制]

18 0 18 0 0 0 11 0 0 0 0 0 0 5 0 0 0 0 0 0 0 2 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

18
0
18 0
0
0
11 0
0
0
0
0
0
5 0
0
0
0
0
0
0
2 0

样例输出1[复制]

16

1

16

代码

#include<cstdio>
#include<iostream>
using namespace std;
bool pd[201];
int father[201];
int n,m;
int find(int x){return father[x]==x? x:father[x]=find(father[x]);}
void un(int x,int y){if(find(x)!=find(y))father[find(x)]=find(y);}
void search(int x)
{
	for(int i=1;i<=n;i++)
        if(find(x)==find(i))pd[i]=1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)father[i]=i;
    for(int i=1;i<=n;i++)
    {
		scanf("%d",&m);
		while(m!=0)
		{
			un(i,m);
			scanf("%d",&m);
		} 
	}
    int ans=0;
    for(int i=1;i<=n;i++)
    {
		if(!pd[i])ans++;
		search(i);
	}
    printf("%d",ans);
    return 0;
}