hdu - 1232 - 畅通工程
题意:N个城镇之间已有M条路,任意2个城镇之间可以建路,问还要建多少条路这N个城镇才能连通。
——>>其实就是求有多少个连通分支,然后减去1就好。
并查集实现:
[cpp]
#include <cstdio>
#include <set>
using namespace std;
const int maxn = 1000 + 10;
int fa[maxn];
int find_set(int i)
{
if(fa[i] == i) return i;
else return (fa[i] = find_set(fa[i]));
}
bool union_set(int x, int y)
{
int root_x = find_set(x);
int root_y = find_set(y);
if(root_x == root_y) return 0;
else fa[root_y] = root_x;
return 1;
}
int main()
{
int N, M, i, x, y;
while(~scanf("%d", &N))
{
if(!N) return 0;
scanf("%d", &M);
for(i = 1; i <= N; i++) fa[i] = i;
for(i = 1; i <= M; i++)
{
scanf("%d%d", &x, &y);
union_set(x, y);
}
set<int> s;
for(i = 1; i <= N; i++) s.insert(find_set(i));
printf("%d\n", s.size()-1);
s.clear();
}
return 0;
}
直接dfs实现:
[cpp]
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 1000 + 10;
int vis[maxn];
vector<int> G[maxn];
void dfs(int u)
{
vis[u] = 1;
int k = G[u].size();
for(int i = 0; i < k; i++) if(!vis[G[u][i]]) dfs(G[u][i]);
}
int main()
{
int N, M, i, x, y;
while(~scanf("%d", &N))
{
if(!N) return 0;
scanf("%d", &M);
for(i = 1; i <= M; i++)
{
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
memset(vis, 0, sizeof(vis));
int cnt = 0; www.zzzyk.com
for(i = 1; i <= N; i++)
if(!vis[i])
{
cnt++;
dfs(i);
}
printf("%d\n", cnt-1);
for(i = 1; i <= N; i++) G[i].clear();
}
return 0;
}
dfs实现最后需要清除图,第一次做vector的这个工作,还是二维数组的,开始用G.clear()是编译错误,换成一行行的清除却又行了!佩服自己。
补充:软件开发 , C++ ,