当前位置 博文首页 > u012938183的博客：公司数量【ybt书上】
【问题描述】
在某个城市里住着n个人， 现在给定关于 n个人的m条信息
（即某2个人认识） ， 假设所有认识（直接或间接认识都算认
识） 的人一定属于同一个公司。
若是某两人不在给出的信息里， 那么他们不认识， 属于两
个不同的公司。
已知人的编号从1至n。
请计算该城市最多有多少公司。
【输入】
第一行： n（<=10000,人数） ，
第二行： m（<=100000， 信息）
以下若干行： 每行两个数： i 和j， 中间一个空格隔开， 表
示i和j相互认识。
【输出】
公司的数量。
方法1：dfs
#include <iostream>
#include <cstdio>
using namespace std;
bool vis[10010];
int mp[10010][10010];
int n, m;
void dfs(int x)
{
vis[x] = true;
for(int i = 1; i <= n; i ++)
{
if(mp[x][i])
{
if(! vis[i])
{
dfs(i);
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++)
{
int x, y;
scanf("%d%d", &x, &y);
mp[x][y] = mp[y][x] = true;
}
int cnt = 0;
for(int i = 1; i <= n; i ++)
{
if(! vis[i])
{
cnt ++;
dfs(i);
}
}
printf("%d\n", cnt);
return 0;
}
方法2：bfs
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int n, m;
int mp[10010][10010];
int vis[10010];
void bfs(int v)
{
queue<int> q;
q.push(v);
vis[v] = true;
while(! q.empty())
{
int f = q.front();
q.pop();
for(int i = 1; i <= n; i ++)
{
if(mp[f][i] && ! vis[i])
{
q.push(i);
vis[i] = true;
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++)
{
int x, y;
scanf("%d%d", &x, &y);
mp[x][y] = mp[y][x] = true;
}
int cnt = 0;
for(int i = 1; i <= n; i ++)
{
if(! vis[i])
{
bfs(i);
cnt ++;
}
}
printf("%d\n", cnt);
return 0;
}
方法3：并查集（不在今天学习的范围内，有兴趣的同学自己研究）
