hdu - 1232 - 畅通工程
题意：N个城镇之间已有M条路，任意2个城镇之间可以建路，问还要建多少条路这N个城镇才能连通。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1232
——>>其实就是求有多少个连通分支，然后减去1就好。
并查集实现：
#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;}dfs实现最后需要清除图，第一次做vector的这个工作，还是二维数组的，开始用G.clear()是编译错误，换成一行行的清除却又行了！佩服自己。