题目描述

给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权值和最小。

请你找到给定图中最小生成树的所有关键边和伪关键边。如果最小生成树中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。

请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。

样例1

输入：n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
输出：[[0,1],[2,3,4,5]]
解释：上图描述了给定图。
下图是所有的最小生成树。
注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出
的第一个列表。
边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。

样例2

输入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
输出：[[],[0,1,2,3]]
解释：可以观察到 4 条边都有相同的权值，任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。

限制

• $2 \leq n \leq 100$
• $1 \leq edges.length \leq min(200, n * (n - 1) / 2)$
• $edges[i].length = 3$
• $0 \leq fromi < toi < n$
• $1 \leq weighti \leq 1000$
• $所有 (fromi, toi) 数对都是互不相同的。$

算法

(最小生成树) $O(m^2log(m))$

1. 先用$Kruskal$算法求最小生成树的边权和$cost$
2. 若边$e$从图中删除后，求得的最小生成树边权之和大于$cost$，说明$e$是关键边
3. 若边$e$不是关键边，那么强制加入这条边，然后再求最小生成树，如果求得的边权和仍然是$cost$，说明$e$只出现在某些或者某个最小生成树中，为伪关键边
4. 注意，题目要求返回的是边的下标，因此需要在边中记录其对应的原始数组的下标

时间复杂度

1. 初始时，预处理边和对边权进行排序的时间分别为$O(m)$和$O(mlog(m))$，$m$为边的条数
2. $Kruskal$算法的时间复杂为$O(n + mlog(m))$
3. 枚举每条边，判断是关键边还是伪关键边，每次判断也要做$Kruskal$算法，时间复杂度为$O(m * (n + mlog(m)))$
4. 所以总的时间复杂度约为$O(m^2log(m))$

C++ 代码

class Solution {
public:
    vector<int> p;

    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    int kruskal_without_k(int n, vector<vector<int>>& edges, int k) {
        for (int i = 0; i < n; i ++ ) p[i] = i;

        int ret = 0, cnt = n;

        for (auto e : edges) {
            int w = e[0], a = e[1], b = e[2], i = e[3];
            if (i == k) continue;
            if (find(a) != find(b)) {
                p[find(a)] = find(b);
                ret += w;
                cnt -- ;
            }
        }

        if (cnt > 1) ret = INT_MAX;
        return ret;
    }

    int kruskal_with_k(int n, vector<vector<int>>& edges, int k) {
        for (int i = 0; i < n; i ++ ) p[i] = i;

        int ret = 0, cnt = n;

        for (auto e : edges) {
            if (e[3] == k) {
                int w = e[0], a = e[1], b = e[2];
                if (find(a) != find(b)) {
                    ret += w;
                    p[find(a)] = find(b);
                    cnt -- ;
                }
                break;
            }
        }

        for (auto e : edges) {
            int w = e[0], a = e[1], b = e[2], i = e[3];
            if (i == k) continue;
            if (find(a) != find(b)) {
                p[find(a)] = find(b);
                ret += w;
                cnt -- ;
            }
        }

        if (cnt > 1) ret = INT_MAX;
        return ret;
    }

    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
        for (int i = 0; i < edges.size(); i ++ ) {
            auto &e = edges[i];
            swap(e[0], e[2]);
            e.push_back(i);
        }

        sort(edges.begin(), edges.end());
        p = vector<int>(n);
        int cost = kruskal_without_k(n, edges, -1);

        vector<vector<int>> ret(2);

        for (int i = 0; i < edges.size(); i ++ ) {
            if (kruskal_without_k(n, edges, i) != cost) ret[0].push_back(i);
            else if (kruskal_with_k(n, edges, i) == cost) ret[1].push_back(i);
        }

        return ret;
    }
};