LeetCode:1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tre找到最小生成树里的关键边和伪关键边（C语言）

喜欢ヅ旅行 2023-01-09 15:37 3阅读 0赞

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

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

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

示例 1：  
![在这里插入图片描述][97653a59aa7a845b58bf9179e6a5866d.png_pic_center]

输入：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\]\]  
解释：上图描述了给定图。  
下图是所有的最小生成树。  
![在这里插入图片描述][f22523204e0560f6ab9ef78b8937b20d.png_pic_center]

注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出的第一个列表。  
边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。

示例 2 ：  
![在这里插入图片描述][816e7f6d3e31615c2d7cc3fa9c3aeec5.png_pic_center]

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

提示：

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

**解答：**

void swap(int* a, int* b) { 
        int tmp = *a;
        *a = *b, *b = tmp;
    }
    
    struct Edge { 
        int x, y, w, id;
    };
    
    int cmp(const void* a, const void* b) { 
        return ((struct Edge*)a)->w - ((struct Edge*)b)->w;
    }
    
    struct DisjointSetUnion { 
        int *f, *size;
        int n, setCount;
    };
    
    void initDSU(struct DisjointSetUnion* obj, int n) { 
        obj->f = malloc(sizeof(int) * n);
        obj->size = malloc(sizeof(int) * n);
        obj->n = n;
        obj->setCount = n;
        for (int i = 0; i < n; i++) { 
            obj->f[i] = i;
            obj->size[i] = 1;
        }
    }
    
    void freeDSU(struct DisjointSetUnion* obj) { 
        free(obj->f);
        free(obj->size);
        free(obj);
    }
    
    int find(struct DisjointSetUnion* obj, int x) { 
        return obj->f[x] == x ? x : (obj->f[x] = find(obj, obj->f[x]));
    }
    
    int unionSet(struct DisjointSetUnion* obj, int x, int y) { 
        int fx = find(obj, x), fy = find(obj, y);
        if (fx == fy) { 
            return false;
        }
        if (obj->size[fx] < obj->size[fy]) { 
            swap(&fx, &fy);
        }
        obj->size[fx] += obj->size[fy];
        obj->f[fy] = fx;
        obj->setCount--;
        return true;
    }
    
    int** findCriticalAndPseudoCriticalEdges(int n, int** edges, int edgesSize, int* edgesColSize, int* returnSize, int** returnColumnSizes) { 
        int m = edgesSize;
        struct Edge edgesTmp[m];
        for (int i = 0; i < m; i++) { 
            edgesTmp[i].x = edges[i][0];
            edgesTmp[i].y = edges[i][1];
            edgesTmp[i].w = edges[i][2];
            edgesTmp[i].id = i;
        }
        qsort(edgesTmp, m, sizeof(struct Edge), cmp);
    
        struct DisjointSetUnion* ufStd = malloc(sizeof(struct DisjointSetUnion));
        initDSU(ufStd, n);
    
        int value = 0;
        for (int i = 0; i < m; ++i) { 
            if (unionSet(ufStd, edgesTmp[i].x, edgesTmp[i].y)) { 
                value += edgesTmp[i].w;
            }
        }
        freeDSU(ufStd);
    
        *returnSize = 2;
        int** ans = malloc(sizeof(int*) * 2);
        for (int i = 0; i < 2; i++) { 
            ans[i] = malloc(sizeof(int) * m);
        }
        *returnColumnSizes = malloc(sizeof(int) * 2);
        memset(*returnColumnSizes, 0, sizeof(int) * 2);
    
        for (int i = 0; i < m; ++i) { 
            // 判断是否是关键边
            struct DisjointSetUnion* uf1 = malloc(sizeof(struct DisjointSetUnion));
            initDSU(uf1, n);
    
            int v = 0;
            for (int j = 0; j < m; ++j) { 
                if (i != j && unionSet(uf1, edgesTmp[j].x, edgesTmp[j].y)) { 
                    v += edgesTmp[j].w;
                }
            }
            if (uf1->setCount != 1 || (uf1->setCount == 1 && v > value)) { 
                ans[0][(*returnColumnSizes)[0]++] = edgesTmp[i].id;
                continue;
            }
            freeDSU(uf1);
    
            // 判断是否是伪关键边
            struct DisjointSetUnion* uf2 = malloc(sizeof(struct DisjointSetUnion));
            initDSU(uf2, n);
            unionSet(uf2, edgesTmp[i].x, edgesTmp[i].y);
            v = edgesTmp[i].w;
            for (int j = 0; j < m; ++j) { 
                if (i != j && unionSet(uf2, edgesTmp[j].x, edgesTmp[j].y)) { 
                    v += edgesTmp[j].w;
                }
            }
            if (v == value) { 
                ans[1][(*returnColumnSizes)[1]++] = edgesTmp[i].id;
            }
        }
        return ans;
    }

**运行结果：**  
![在这里插入图片描述][20210121215352296.png_pic_center]

**Notes：**  
参考官方文档：[https://leetcode-cn.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/solution/zhao-dao-zui-xiao-sheng-cheng-shu-li-de-gu57q/][https_leetcode-cn.com_problems_find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree_solution_zhao-dao-zui-xiao-sheng-cheng-shu-li-de-gu57q]

[97653a59aa7a845b58bf9179e6a5866d.png_pic_center]: /images/20221119/21a90392195f4a29bb54cb609d91def1.png
[f22523204e0560f6ab9ef78b8937b20d.png_pic_center]: /images/20221119/758340cb76bd46bc989e90ae2bbc1623.png
[816e7f6d3e31615c2d7cc3fa9c3aeec5.png_pic_center]: /images/20221119/74585603b625443189d1a2d1bdf980f5.png
[20210121215352296.png_pic_center]: /images/20221119/fb8ca4a121984210835cf4a5f1b5a965.png
[https_leetcode-cn.com_problems_find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree_solution_zhao-dao-zui-xiao-sheng-cheng-shu-li-de-gu57q]: https://leetcode-cn.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/solution/zhao-dao-zui-xiao-sheng-cheng-shu-li-de-gu57q/