題意：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.2cto.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()是編譯錯誤，換成一行行的清除卻又行了！佩服自己。
