C++ 公司数量 正解

题目描述

在某个城市里住着 n 个人，现在给定关于 n 个人的 m 条信息（即某 2 个人认识），假设所有认识（直接或间接认识都算认识）的人一定属于同一个公司。

若是某两人不在给出的信息里，那么他们不认识，属于两个不同的公司。

已知人的编号从 1 至  n。

请计算该城市最多有多少公司。

输入

第一行：n（<=100,人数），

第二行：m（<=100，信息）

以下 m 行：每行两个数：i 和 j，中间一个空格隔开，表示 i 和 j 相互认识。

输出

输出一个正整数，代表公司的数量。

样例输入

11 
9 
1 2 
4 5 
3 4 
1 3 
5 6 
7 10 
5 10 
6 10 
8 9  

样例输出 

3


正解：

 1 #include <cstdio>
 2 using namespace std;
 3 const int N=105,M=105;
 4 int h[N],w[M],e[M],ne[M],idx,g[N][N],cnt,n,m,x,y,z;
 5 bool v[N];
 6 void dfs(int k)
 7 {
 8     v[k]=1;
 9     for(int i=1;i<=n;i++)
10     {
11         if(g[k][i]==1&&!v[i]) 
12         {
13             v[i]=1;
14             dfs(i);
15         }
16     }
17     return ;
18 }
19 int main()
20 {
21     scanf("%d%d",&n,&m);
22     for(int i=1;i<=m;i++)
23     {
24         scanf("%d%d",&x,&y);
25         g[x][y]=1;
26         g[y][x]=1;
27     }
28     for(int i=1;i<=n;i++)
29     {
30         if(v[i]==0)
31         {
32             cnt++;
33             dfs(i);    
34         }
35     }
36     printf("%d",cnt);
37     return 0;
38 }