LeetCode:1579. Remove Max Number of Edges to Keep Graph Fully Traversable保证图可完全遍历(C语言）

浅浅的花香味﹌ 2023-01-11 14:27 93阅读 0赞

**题目描述：**  
Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3 种类型的边：

类型 1：只能由 Alice 遍历。
    类型 2：只能由 Bob 遍历。
    类型 3：Alice 和 Bob 都可以遍历。

给你一个数组 edges ，其中 edges\[i\] = \[typei, ui, vi\] 表示节点 ui 和 vi 之间存在类型为 typei 的双向边。请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。

返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。

示例 1：  
\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QGroId5d-1611709674627)(https://assets.leetcode.com/uploads/2020/08/19/ex1.png\#pic\_center)\]

输入：n = 4, edges = \[\[3,1,2\],\[3,2,3\],\[1,1,3\],\[1,2,4\],\[1,1,2\],\[2,3,4\]\]  
输出：2  
解释：如果删除 \[1,1,2\] 和 \[1,1,3\] 这两条边，Alice 和 Bob 仍然可以完全遍历这个图。再删除任何其他的边都无法保证图可以完全遍历。所以可以删除的最大边数是 2 。

示例 2：  
\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7HrLrpU3-1611709687193)(https://assets.leetcode.com/uploads/2020/08/19/ex2.png\#pic\_center)\]

输入：n = 4, edges = \[\[3,1,2\],\[3,2,3\],\[1,1,4\],\[2,1,4\]\]  
输出：0  
解释：注意，删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。

示例 3：  
![在这里插入图片描述][ba2895612059f62f5dee86ca4936f7a5.png_pic_center]

输入：n = 4, edges = \[\[3,2,3\],\[1,1,2\],\[2,3,4\]\]  
输出：-1  
解释：在当前图中，Alice 无法从其他节点到达节点 4 。类似地，Bob 也不能达到节点 1 。因此，图无法完全遍历。

提示：

1 <= n <= 10^5
    1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)
    edges[i].length == 3
    1 <= edges[i][0] <= 3
    1 <= edges[i][1] < edges[i][2] <= n
    所有元组 (typei, ui, vi) 互不相同

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

void swap(int* a, int* b) { 
        int tmp = *a;
        *a = *b, *b = tmp;
    }
    
    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;
        }
    }
    
    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 maxNumEdgesToRemove(int n, int** edges, int edgesSize, int* edgesColSize) { 
        struct DisjointSetUnion* ufa = malloc(sizeof(struct DisjointSetUnion));
        initDSU(ufa, n);
        struct DisjointSetUnion* ufb = malloc(sizeof(struct DisjointSetUnion));
        initDSU(ufb, n);
        int ans = 0;
    
        // 节点编号改为从 0 开始
        for (int i = 0; i < edgesSize; i++) { 
            edges[i][1]--;
            edges[i][2]--;
        }
    
        // 公共边
        for (int i = 0; i < edgesSize; i++) { 
            if (edges[i][0] == 3) { 
                if (!unionSet(ufa, edges[i][1], edges[i][2])) { 
                    ++ans;
                } else { 
                    unionSet(ufb, edges[i][1], edges[i][2]);
                }
            }
        }
    
        // 独占边
        for (int i = 0; i < edgesSize; i++) { 
            if (edges[i][0] == 1) { 
                // Alice 独占边
                if (!unionSet(ufa, edges[i][1], edges[i][2])) { 
                    ++ans;
                }
            } else if (edges[i][0] == 2) { 
                // Bob 独占边
                if (!unionSet(ufb, edges[i][1], edges[i][2])) { 
                    ++ans;
                }
            }
        }
    
        if (ufa->setCount != 1 || ufb->setCount != 1) { 
            return -1;
        }
        return ans;
    }

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

[ba2895612059f62f5dee86ca4936f7a5.png_pic_center]: /images/20221119/bbfe34bc661a47daa084d129d2e1cf1f.png
[20210127090654559.png_pic_center]: /images/20221119/faf2e82214b24a398e8c024c1b0a5669.png