无脑总统的火星国

时间:2022-11-06 11:27:01

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;

}