题目描述
在某个城市里住着 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 }
标签:10,int,样例,C++,认识,数量,公司,105
From: https://www.cnblogs.com/766hjkasd/p/17724416.html