hdu - 1232 - 畅通工程

题意：N个城镇之间已有M条路，任意2个城镇之间可以建路，问还要建多少条路这N个城镇才能连通。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1232

——>>其实就是求有多少个连通分支，然后减去1就好。

并查集：

#include <cstdio>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);}int cnt = 0;for(i = 1; i <= N; i++) if(fa[i] == i) cnt++;printf("%d\n", cnt-1);}return 0;
}

并查集 + set 实现：

#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;
}

#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;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;
}