1579. 保证图可完全遍历

 

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: 输入: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: 输入:n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]] 输出:0 解释:注意,删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。 示例 3: 输入:n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]] 输出:-1 解释:在当前图中,Alice 无法从其他节点到达节点 4 。类似地,Bob 也不能达到节点 1 。因此,图无法完全遍历。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

 

官方题解: https://leetcode-cn.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/solution/bao-zheng-tu-ke-wan-quan-bian-li-by-leet-mtrw/

 

1579. 保证图可完全遍历
  1 // 并查集模板
  2 
  3 class UnionFind{
  4 public:
  5     vector<int>  parent;
  6     vector<int> size;
  7     int n;
  8     //当前联通分量数目
  9     int setCount;
 10 
 11 public:
 12     UnionFind(int _n):n(_n),setCount(_n),parent(_n),size(_n,1){
 13         iota(parent.begin(), parent.end(), 0);
 14     }
 15 
 16     int findset(int x){
 17         return parent[x] == x ? x : parent[x] = findset(parent[x]);
 18     }
 19 
 20     bool unite(int x, int y)
 21     {
 22         x = findset(x);
 23         y = findset(y);
 24         if(x == y)
 25         {
 26             return false;
 27         }
 28         if(size[x] < size[y])
 29         {
 30             swap(x,y);
 31         }
 32         parent[y] = x;
 33         size[x] += size[y];
 34         --setCount;
 35         return true;
 36     }
 37 
 38     bool connected(int x, int y)
 39     {
 40         x = findset(x);
 41         y = findset(y);
 42         return x == y;
 43     }
 44 };
 45 
 46 
 47 class Solution {
 48 public:
 49     int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
 50         UnionFind ufa(n), ufb(n);
 51         int ans = 0;
 52 
 53         //结点编号改为从0开始 
 54         for(auto & edge:edges)
 55         {
 56             --edge[1];
 57             --edge[2];
 58         }
 59 
 60         //公共边
 61         for(const auto& edge:edges)
 62         {
 63             if(edge[0]==3)
 64             {
 65                 if(!ufa.unite(edge[1], edge[2]))
 66                 {
 67                     ++ans;
 68                 }
 69                 else
 70                 {
 71                     ufb.unite(edge[1], edge[2]);
 72                 }
 73             }
 74         }
 75 
 76         //独占边 
 77         for(const auto& edge: edges)
 78         {
 79             if(edge[0] == 1)
 80             {
 81                 //Alice 独占边
 82                 if(!ufa.unite(edge[1], edge[2]))
 83                 {
 84                     ++ans;
 85                 }
 86             }
 87             else if (edge[0]==2)
 88             {
 89                 //Bob 独占边
 90                 if(!ufb.unite(edge[1], edge[2]))
 91                 {
 92                     ++ans;
 93                 }
 94             }
 95         }
 96 
 97         if(ufa.setCount != 1 || ufb.setCount != 1)
 98         {
 99             return -1;
100         }
101         return ans;
102     }
103 };
并查集--先思考再看代码

 

上一篇:高级程序员——面试的问题系列:密码算法的想干问题


下一篇:蓝桥杯练习题