1579. 保证图可完全遍历

难度困难118
Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3 种类型的边：

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

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

示例 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：
并查集 - 图2
输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
输出：0
解释：注意，删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。

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

  1. //简化问题：
  2. //去掉AB：那么就是去掉多少条边，这个图还能连通
  3. //再去：有多少条边是多余的 
  4. class Djset {
  5. private:
  6.     vector<int> parent;
  7.     vector<int> rank;
  8.     int count;
  9.     int rest;
  10. public:
  11.     Djset(int n):parent(vector<int> (n)), rank(vector<int> (n)), count(n), rest(0)
  12.     {
  13.         for(int i = 0; i < n; ++ i)
  14.             parent[i] = i;
  15.     }
  16.     int find(int x)
  17.     {
  18.         if(x != parent[x])
  19.             parent[x] = find(parent[x]);
  20.         return parent[x];
  21.     }
  22.     void merge(int x, int y)
  23.     {
  24.         int rootx = find(x);
  25.         int rooty = find(y);
  26.         if(rootx != rooty){
  27.             if(rank[rootx] < rank[rooty])
  28.                 swap(rootx, rooty);
  29.             parent[rooty] = rootx;
  30.             count --;
  31.             if(rank[rootx] == rank[rooty]) rank[rootx] += 1;
  32.         }else
  33.             ++ rest;
  34.     }
  35.     int getCount()
  36.     {
  37.         return count;
  38.     }
  39.     int getRest()
  40.     {
  41.         return rest;
  42.     }
  43. };
  44. class Solution {
  45. public:
  46.     int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
  47.         for(auto &e: edges)
  48.             e[1] -= 1, e[2] -= 1;
  49.         //ab分别的并查集
  50.         Djset ds(n);
  51.         //情况3: Alice和Bob都可以遍历
  52.         for(const auto& c: edges)
  53.         {
  54.             if(c[0] == 3){
  55.                 ds.merge(c[1], c[2]);
  56.             }
  57.         }
  58.         Djset dsa = ds;
  59.         Djset dsb = ds;
  60.         for(const auto& c: edges)
  61.         {
  62.             if(c[0] == 1){
  63.                 dsa.merge(c[1], c[2]);
  64.             }
  65.             else if(c[0] == 2){
  66.                 dsb.merge(c[1], c[2]);
  67.             }
  68.         }
  69.         if(dsa.getCount() != 1 || dsb.getCount() != 1)
  70.             return -1;
  71.         return dsa.getRest() + dsb.getRest() - ds.getRest();
  72.     }
  73. };