【每日一题】 1579. 保证图可完全遍历

淩亂°似流年 2022-10-27 12:17 104阅读 0赞

# 【每日一题】 1579. 保证图可完全遍历 #

> 避免每日太过咸鱼，一天搞定一道LeetCode算法题

## 一、题目描述 ##

难度： **困难**

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 <= 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) 互不相同

**示例 1：**

![在这里插入图片描述][2021020409353891.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：**

![在这里插入图片描述][20210204093531533.png_pic_center]

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

**示例 3：**

![在这里插入图片描述][20210204093524153.png_pic_center]

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

## 二、题解 ##

### 1. 解法 ###

### **解题思路：** ###

我们称类型1,2,3 的边分别为「Alice 独占边」「Bob 独占边」以及「公共边」。

首先我们需要思考什么样的图是可以被 Alice 和 Bob 完全遍历的。对于 Alice 而言，她可以经过的边是「Alice 独占边」以及「公共边」，由于她需要能够从任意节点到达任意节点，那么就说明：

> 当图中仅有「Alice 独占边」以及「公共边」时，整个图是连通的，即整个图只包含一个连通分量。

同理，对于 Bob 而言，当图中仅有「Bob 独占边」以及「公共边」时，整个图也要是连通的。

由于题目描述中希望我们删除最多数目的边，这等价于保留最少数目的边。换句话说，我们可以从一个仅包含 nn 个节点（而没有边）的无向图开始，逐步添加边，使得满足上述的要求。

那么我们应该按照什么策略来添加边呢？直觉告诉我们，「公共边」的重要性大于「Alice 独占边」以及「Bob 独占边」，因为「公共边」是 Alice 和 Bob 都可以使用的，而他们各自的独占边却不能给对方使用。「公共边」的重要性也是可以证明的：

> 对于一条连接了两个不同的连通分量的「公共边」而言，如果我们不保留这条公共边，那么 Alice 和 Bob 就无法往返这两个连通分量，即他们分别需要使用各自的独占边。因此，Alice 需要一条连接这两个连通分量的独占边，Bob 同样也需要一条连接这两个连通分量的独占边，那么一共需要两条边，这就严格不优于直接使用一条连接这两个连通分量的「公共边」了。

因此，我们可以遵从优先添加「公共边」的策略。具体地，我们遍历每一条「公共边」，对于其连接的的两个节点：

*  如果这两个节点在同一个连通分量中，那么添加这条「公共边」是无意义的；
 *  如果这两个节点不在同一个连通分量中，我们就可以（并且一定）添加这条「公共边」，然后合并这两个节点所在的连通分量。

这就提示了我们使用并查集来维护整个图的连通性，上述的策略只需要用到并查集的「查询」和「合并」这两个最基础的操作。

在处理完了所有的「公共边」之后，我们需要处理他们各自的独占边，而方法也与添加「公共边」类似。我们将当前的并查集复制一份，一份交给 Alice，一份交给 Bob。随后 Alice 不断地向并查集中添加「Alice 独占边」，Bob 不断地向并查集中添加「Bob 独占边」。在处理完了所有的独占边之后，如果这两个并查集都只包含一个连通分量，那么就说明 Alice 和 Bob 都可以遍历整个无向图。

**细节**

在使用并查集进行合并的过程中，我们每遇到一次失败的合并操作（即需要合并的两个点属于同一个连通分量），那么就说明当前这条边可以被删除，将答案增加 1。

public static void main(String[] args) { 
        int n = 4;
        int[][] edges = new int[][]{ { 3, 1, 2}, { 3, 2, 3}, { 1, 1, 3}, { 1, 2, 4}, { 1, 1, 2}, { 2, 3, 4}};
        int i = maxNumEdgesToRemove(n, edges);
        System.out.println("最大删除：" + i);
    }
    
    public static int maxNumEdgesToRemove(int n, int[][] edges) { 
        // 初始化并查集对象
        DisjointSetUnion uniona = new DisjointSetUnion(n);
        DisjointSetUnion unionb = new DisjointSetUnion(n);
        int count = 0;
    
        // 节点编号改为从 0 开始
        for (int[] edge : edges) { 
            --edge[1];
            --edge[2];
        }
    
        // 遍历获取type为3的边
        for (int i = 0; i < edges.length; i++) { 
            if (edges[i][0] == 3) { 
                // 判断当前节点是否已经在联通 可以联通证明该边可以删除 不可以联通 则加入该图中
                if (uniona.query(edges[i][1], edges[i][2])) { 
                    System.out.println("边：" + i + "可以删除");
                    count++;
                } else { 
                    unionb.merge(edges[i][1], edges[i][2]);
                    uniona.merge(edges[i][1], edges[i][2]);
                }
            }
        }
    
        // 遍历获取独占边
        for (int i = 0; i < edges.length; i++) { 
            if (edges[i][0] == 1) { 
                // Alice 独占边
                if (!uniona.merge(edges[i][1], edges[i][2])) { 
                    System.out.println("Alice 独占边：" + i + "可以删除");
                    ++count;
                }
            } else if (edges[i][0] == 2) { 
                // Bob 独占边
                if (!unionb.merge(edges[i][1], edges[i][2])) { 
                    System.out.println("Bob 独占边：" + i + "可以删除");
                    ++count;
                }
            }
        }
    
        if (uniona.setCount != 1 || unionb.setCount != 1) { 
            return -1;
        }
    
        return count;
    }
    
    static class DisjointSetUnion { 
        int[] f;
        int[] rank;
        // 当前连通分量数目
        int setCount;
    
        public DisjointSetUnion(int n) { 
            this.setCount = n;
            this.f = new int[n];
            this.rank = new int[n];
            for (int i = 0; i < f.length; i++) { 
                f[i] = i;
                rank[i] = 1;
            }
        }
    
        public int find(int x) { 
            return f[x] == x ? x : (f[x] = find(f[x]));
        }
    
        public boolean merge(int x, int y) { 
            int fx = f[x], fy = f[y];
            if (fx == fy) { 
                return false;
            }
            if (rank[fx] <= rank[fy]) { 
                f[fx] = f[fy];
            } else { 
                f[fy] = f[fx];
            }
            if (rank[fx] == rank[fy] && fx != fy) { 
                rank[fy]++;
            }
            --setCount;
            return true;
        }
    
        public boolean query(int x, int y) { 
            return find(x) == find(y);
        }
    }

题目来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/distance-between-bus-stops

\--------------最后感谢大家的阅读，愿大家技术越来越流弊！--------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]

\--------------也希望大家给我点支持，谢谢各位大佬了！！！--------------

[2021020409353891.png_pic_center]: /images/20221024/003bbc903cca4e8a95b15e16a482e2c6.png
[20210204093531533.png_pic_center]: /images/20221024/c3dac5264a024d0bb15314324396758b.png
[20210204093524153.png_pic_center]: /images/20221024/50ebaff1946949b28fcf00b022fefe57.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]: /images/20221024/dd783df5dbb446bba4ffa0927ae13558.png