通畅工程（并查集的运用）

畅通工程（并查集的运用）

题目描述如下：

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省*“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

输入：第一行给出两个整数，分别是城镇数目N(<1000)和道路数目M, 随后的M行对应着M条道路，每行给出一对正整数。，分别表示这条道路连通的两个城市的编号。为简单起见，城镇编号从1到N。注意，两个城市之间可以有多条道路联通。如下：

当N为0时，输入结束，该例子不用处理。输入文件如下：

输出文件如下：

0 
2 
998

分析：

该题考察的是并查集的运用。即求整幅图的连通性问题。也就是说，这幅图有几个联通分支。

如果是一个连通分量，说明整幅图的点都连接起来了，不用再修路了。如果有两个连通分量，则只需要修一条路。从这两个连通分量中分别任意选取一个点，连接起来即可。如果有n 个连通分量，只需再修n -1 条路即可。

下面利用并查集合求解如下：

#include <iostream>
#include <fstream>

using namespace std;

const int MAX = 1000 + 5;
int parent[MAX];

void Make_Set(int N) {
    for(int i = 1; i <= N; ++i) {
        parent[i] = i;
    }
}

int Find_Set(int x) {
    while(parent[x] != x) { // 找到x 所在集合的代表元素
        x = parent[x];
    }
    return x;
}

void UNION(int x, int y) {
    int rootX = Find_Set(x);
    int rootY = Find_Set(y);

    if(rootX != rootY) {
        parent[rootX] = rootY;
    }
}

int main() {
    int N, M, x, y, res;

    ifstream input("in.txt");
    ofstream output("out.txt");

    while(input >> N >> M) {
        Make_Set(N);

        for(int i = 1; i <= M; ++i) {
            input >> x >> y;
            UNION(x, y);
        }

        res = 0;

        for(int i = 1; i <= N; ++i) { // 统计连通分量个数
            if(parent[i] == i) {
                res++;
            }
        }

        output << res - 1 << endl;
    }
    return 0;
}

运行结果如下：

通畅工程（并查集的运用）

优化办法：

对于并查集，有两种优化策略。

优化策略1：按秩合并策略。这一优化是针对合并的。作用是避免了合并时产生糟糕的情况。方法是将深度小的树合并到深度达的树。

假设两个树的深度分别为 h1 和 h2，则合并后树的高度h 如下：

if(h1 != h2) max(h1, h2)

if(h1 == h2) h1 + 1

效果是使得合并之后，包含k个节点的树的最大高度不超过 floor(logk)。

进一步优化：优化策略是路径压缩。是针对Find进行优化的。通过路径压缩，可以减少每次寻找根节点的次数，使得我们的树更加的flat。

步骤：第一步找到根节点

第二步，修改查找路径上的所有节点，将他们只想根节点。

通畅工程（并查集的运用）

优化之后的程序如下：

#include <iostream>
#include <fstream>

using namespace std;

const int MAX = 1000 + 5;
struct Node {
    int parent;
    int Rank;
};
Node node[MAX];

void Make_Set(int N) {
    for(int i = 1; i <= N; ++i) {
        node[i].parent = i;
        node[i].Rank = 0;
    }
}
int Find_Set(int x) { // 查找所属集合并压缩搜索路径
    if(x == node[x].parent) { // 找到x 所在集合的代表元素
        return x;
    }
    else
        node[x].parent = Find_Set(node[x].parent);
    return node[x].parent;
}


void UNION(int x, int y) {
    int rootX = Find_Set(x);
    int rootY = Find_Set(y);

    if(rootX == rootY) return; // 同一个集合中
    else {
        if(node[rootX].Rank == node[rootY].Rank) {
            node[rootX].parent = rootY;
            node[rootY].Rank++;
        }
        else if(node[rootX].Rank > node[rootY].Rank)
            node[rootY].parent = rootX;
        else
            node[rootX].parent = rootY;
    }
}

int main() {
    int N, M, x, y, res;

    ifstream input("in.txt");
    ofstream output("out.txt");

    while(input >> N >> M) {
        Make_Set(N);

        for(int i = 1; i <= M; ++i) {
            input >> x >> y;
            UNION(x, y);
        }

        res = 0;

        for(int i = 1; i <= N; ++i) { // 统计连通分量个数
            if(node[i].parent == i) {
                res++;
            }
        }

        output << res - 1 << endl;
    }
    return 0;
}

运行后结果同上。

通畅工程（并查集的运用）

相关推荐