问题

LeetCode #1489

本题其实就是三个问题。求最小生成树、不含某条边的最小生成树(可能有也可能没有),一定含某条边的最小生成树。详细分析可见LeetCode上的题解。

解决

因为本题考查的是边,因此用针对边的Kruskal算法即可,这样都不用转换图的表示形式,直接用给定的边集即可。

Kruskal其实属于贪心算法。

Kruskal算法中加入新边时需要考查两个点是否已经被连接,根据网上资料,这个问题可用并查集高效解决。

最后,在代码实现上,我写了一个Kruskal类和一个DSU(Disjoint Set Union,并查集)类(带路径压缩)。借助二者即可完成Solution类。

之所以DSU类中写了两个findFather,是因为我一开始写的是非递归的版本(数据大时可防止爆栈),但是可能因为其中使用的Stack增加了时间复杂度,LeetCode上超时。之后改成了递归版本即可通过。整个速度稍慢,不知道是不是因为使用了很多STL模板而LeetCode没开O2优化的原因。

class DSU   // Disjoint Set Union
{
    vector<int> fathers;

public:
    DSU(const int n)
    {   // initialize
        for (int i = 0; i < n; i++)
            fathers.push_back(i);
    }

    DSU() = default;

    void init(const int n)
    {
        if (fathers.size())
            return;
        for (int i = 0; i < n; i++)
            fathers.push_back(i);
    }

    int findFather(const int x)
    {
        if (fathers[x] == x)
            return x;
        else
        {
            fathers[x] = findFather(fathers[x]);
            return fathers[x];
        }
    }

    int findFather2(const int x)
    {
        int now = x, father = fathers[x];
        stack<int> to_modify;
        while (now != father)
        {
            to_modify.push(now);
            now = father;
            father = fathers[father];
        }
        while (!to_modify.empty())
        {
            fathers[to_modify.top()] = father;
            to_modify.pop();
        }
        return father;
    }

    bool unionTwo(const int x, const int y)
    {
        int x_father = findFather(x), y_father = findFather(y);
        if (x_father == y_father)
            return false;
        else
        {
            fathers[y_father] = fathers[x_father];
            return true;
        }
    }

};

class Kruskal
{
    int n;
    vector<vector<int>>& edges;
    vector<int> tree;
    int exist_edge;
    int del_edge;
    int total;
    DSU dsu;

public:
    Kruskal() = default;

    Kruskal(const int _n, vector<vector<int>>& _edges, const int _exist_edge, const int _del_edge):
        n(_n), edges(_edges), exist_edge(_exist_edge), del_edge(_del_edge), total(0)
    {
        dsu.init(n);
        if (exist_edge != -1)
        {
            tree.push_back(exist_edge);
            auto &e = edges[exist_edge];
            total += e[2];
            dsu.unionTwo(e[0], e[1]);
        }
        mst();
    }

    int mst()
    {
        for (int i = 0; i < edges.size(); i++)
        {
            if (i != exist_edge && i != del_edge)
            {
                if (dsu.findFather(edges[i][0]) != dsu.findFather(edges[i][1]))
                {
                    tree.push_back(i);
                    dsu.unionTwo(edges[i][0], edges[i][1]);
                    total += edges[i][2];
                }
            }
            if (tree.size() == n - 1)
                return total;
        }
        total = -1;
        return -1;
    }

    int total_value()
    {
        return total;
    }
};

class Solution
{
    static bool cmp(vector<int>& x, vector<int>& y)
    {
        return x[2] < y[2];
    }
public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges)
    {
        for (int i = 0; i < edges.size(); i++)
        {
            edges[i].push_back(i);  // e[i] = {from, to, w, index}
        }
        sort(edges.begin(), edges.end(), cmp);
        vector< vector<int> > ans(2);
        int mst = Kruskal(n, edges, -1, -1).total_value();
        for (int i = 0; i < edges.size(); i++)
        {
            auto& e = edges[i];
            int mst_del_e = Kruskal(n, edges, -1, i).total_value();
            if (mst_del_e == -1 || mst_del_e > mst)
                ans[0].push_back(e[3]);
            else
            {
                int mst_exist_e = Kruskal(n, edges, i, -1).total_value();
                if (mst_exist_e == mst)
                    ans[1].push_back(e[3]);
            }
        }
        return ans;
    }
};

参考资料:
最小生成树与并查集(leetcode684,685, 721)
算法学习笔记(1) : 并查集

Last modification:June 27th, 2020 at 03:26 pm
如果觉得我的文章对你有用,请随意赞赏