Description
火星上有这样一个国家,国家总统的名字叫无脑总统(你瞧这名字起的),他对这个国家的省份的划分是很奇特的,那个无脑总统按省与省之间是没有公路来划分的(这样要不军阀割据就怪了,怪不得叫无脑总统呢,确实无脑,呵呵)。现在给出了一些城市的信息,即这个国家城市的个数,以及城市之间的联系也就是哪个城市与哪个城市之间有公路连接。无脑总统很笨,所以聘请你哈工程的Acmer来帮他算一下划分成多少个省份。
Input
有多组测试数据。每组测试数据的第一行有一个正整数N(N<=100),说明这个国家有N个城市。编号分别为1,2.....N.接下来有N行。每行开始有一个正整数M,说明第i个城市与其他M个城市相连,接下来在同一行输入M个数,代表与这个城市相连的城市编号。
Output
让你求出这个国家应该划分成多少个省份。
Sample Input
4
1 2
2 3 4
1 2
1 2
Sample Output
1
答案:
#include<iostream>
using namespace std;
int map[105][105];
int n,m,many,t;
bool can[105];
int dfs(int s);
int main(int argc,char* argv[])
{
int i,j;
while(scanf("%d",&n)!=EOF)
{
many = 0;
memset(can,0,sizeof(can));
memset(map,0,sizeof(map));
for(i=1;i<=n;i++)
{
scanf("%d",&m);
for(j=1;j<=m;j++)
{
scanf("%d",&t);
map[i][t] = 1;
map[t][i] = 1;
}
}
for(i=1;i<=n;i++)
if(!can[i])
many += dfs(i);
cout<<many<<endl;
}
return 0;
}
int dfs(int x)
{
can[x] = 1;
for(int i=1;i<=n;i++)
if(map[x][i] && !can[i])
dfs(i);
return 1;
}