C++刷LeetCode（1579. 保证图可完全遍历）【并查集】【图】

糖逗

题目描述：

1. Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3  种类型的边：
   
2. 
   
3. 类型 1：只能由 Alice 遍历。
   
4. 类型 2：只能由 Bob 遍历。
   
5. 类型 3：Alice 和 Bob 都可以遍历。
   
6. 给你一个数组 edges ，其中 edges[i] = [typei, ui, vi] 表示节点 ui 和 vi 之间存在类型为 typei 的双向边。请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。
   
7. 
   
8. 返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。
   
9. 
   
10.  
    
11. 
    
12. 示例 1：
    
13. 
    
14. 
    
15. 
    
16. 输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
    
17. 输出：2
    
18. 解释：如果删除 [1,1,2] 和 [1,1,3] 这两条边，Alice 和 Bob 仍然可以完全遍历这个图。再删除任何其他的边都无法保证图可以完全遍历。所以可以删除的最大边数是 2 。
    
19. 示例 2：
    
20. 
    
21. 
    
22. 
    
23. 输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
    
24. 输出：0
    
25. 解释：注意，删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。
    
26. 示例 3：
    
27. 
    
28. 
    
29. 
    
30. 输入：n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
    
31. 输出：-1
    
32. 解释：在当前图中，Alice 无法从其他节点到达节点 4 。类似地，Bob 也不能达到节点 1 。因此，图无法完全遍历。
    
33.  
    
34. 
    
35. 提示：
    
36. 
    
37. 1 <= n <= 10^5
    
38. 1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)
    
39. edges[i].length == 3
    
40. 1 <= edges[i][0] <= 3
    
41. 1 <= edges[i][1] < edges[i][2] <= n
    
42. 所有元组 (typei, ui, vi) 互不相同
    
43. 
    
44. 来源：力扣（LeetCode）
    
45. 链接：https://leetcode-cn.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable
    
46. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. private:
   
3.     vector<int>father1;
   
4.     vector<int>father2;
   
5. public:
   
6.     int find_root(int x, vector<int>& par){
   
7.         int root = x;
   
8.         while(par[root]!=root){
   
9.             root = par[root];
   
10.         }
    
11.         while(par[x]!=root){
    
12.             int tmp = par[x];
    
13.             par[x] = root;
    
14.             x = tmp;
    
15.         }
    
16.         return root;
    
17.     }
    
18. 
    
19.     bool merge(int x, int y, vector<int>& father){
    
20.         int temp1 = find_root(x, father);
    
21.         int temp2 = find_root(y, father);
    
22.         if(temp1 != temp2){
    
23.             father[temp1] = temp2;
    
24.             return true;
    
25.         }
    
26.         return false;
    
27.     }
    
28.     int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
    
29.         //并查集
    
30.         //初始化father
    
31.         father1 = vector<int>(n+1, 0);
    
32.         
    
33.         for(int i = 1; i <= n; i++){
    
34.             father1[i] = i;
    
35.         }
    
36.         int res = 0;
    
37.         int node1_nums = 1;
    
38.         //先合并第三种边
    
39.         for(auto cha : edges){
    
40.             if(cha[0] == 3){
    
41.                 if(!merge(cha[1], cha[2], father1)){
    
42.                     //没有合并
    
43.                     res++;
    
44.                 }else{
    
45.                     //合并了
    
46.                     node1_nums++;
    
47.                 }
    
48.             }
    
49.         }
    
50.         father2 = father1;
    
51.         int node2_nums = node1_nums;
    
52.         //合并前两种边
    
53.         for(auto cha : edges){
    
54.             if(cha[0] == 1){
    
55.                 if(!merge(cha[1], cha[2], father1)){
    
56.                     //没有合并
    
57.                     res++;
    
58.                 }else{
    
59.                     node1_nums++;
    
60.                 }
    
61.             }else if(cha[0] == 2){
    
62.                 if(!merge(cha[1], cha[2], father2)){
    
63.                     res++;
    
64.                 }else{
    
65.                     node2_nums++;
    
66.                 }
    
67.             }
    
68.         }
    
69.         if(node1_nums != n || node2_nums != n)return -1;
    
70.         return res;
    
71.     }
    
72. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -di-san-chong-lei-/

https://leetcode-cn.com/problems ... icezai-kan-bo-kavo/