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++ ,