0685 - Redundant Connection II
题干
破题
这题说难不难，没有复杂的数据结构和算法，但是情况比较繁琐细致，可以说非常贴近实际情况了。
具体来说，这个题的破题的关键在于搞清楚一棵有向树，多了一条边后，会形成什么样的情况。这不是一次就能全想清楚的 ，在代码失败了几次后，我们总结出三种情况：
- 形成双头节点（a->b, c->b, b就是双头节点）
- 形成循环（a->b, b->c, c->a）
- 形成带双头节点的环（a->b, b->c, c->a, d->b）
双头节点容易检测出来，循环也可以检测出来，但是如何选择删除的边值得考虑：前两种情况都是删除最后的边即可，但第三种情况必须删除双头节点在环上的边，而不管它的顺序，这样才能同时消除环和双头节点。这是本题繁琐的地方。
解 ①：一般图
思路
按照一般图的做法，不管三七二十一，先根据输入建立邻接表，以及反向引用的表。
这样的话，首先在反向引用表建立的过程，就能检出双头节点，如果它存在的话；
然后可以根据出度与入度，判断双头节点是否有在环上的边，在检测出度入度的时候要单独考虑两个点的环的情况；
最后检出环上边，返回最后一条。
Python 实现
from typing import List
# O(n)
def findRedundantDirectedConnection(edges: List[List[int]]) -> List[int]:
vmap = {} # vertice map
rvmap = {} # recersed vertice map
from enum import Enum
class Mode(Enum):
Ein1 = 1
Ein2 = 2
mode = Mode.Ein1
start = None
end = None
# O(E)
for u,v in edges:
l = vmap.get(u, [])
l.append(v)
vmap[u] = l
if rvmap.get(v):
mode = Mode.Ein2
start = u
end = v
else:
rvmap[v] = u
if mode is Mode.Ein2:
def outd(v):
return len(vmap.get(v, []))
def ind(v):
return 0 if rvmap.get(v) is None else 1
start2 = rvmap[end]
if start in vmap.get(end, []):
return [start, end]
if start2 in vmap.get(end, []):
return [start2, end]
if ind(start) == 0 and outd(start) == 1:
return [start2, end]
if ind(start2) == 0 and outd(start2) == 1:
return [start, end]
# then anyway, use the latter (no cycle)
return [start, end]
# Exact one circle structure
cirset = set()
def is_circle_v(u, visset):
nonlocal cirset
visset.add(u)
l = vmap.get(u, [])
if len(l) == 0: # Noncircle
return False
else:
for v in l:
if v in visset:
cirset = visset
return True
for v in l:
if is_circle_v(v, visset):
return True
return False
for v in vmap.keys():
if is_circle_v(v, set()):
break
for u,v in reversed(edges):
if u in cirset and v in cirset:
return [u, v]
if __name__ == '__main__':
data = [
([4, 1], [[1,2],[2,3],[3,4],[4,1],[1,5]]),
([2, 1], [[2,1],[3,1],[4,2],[1,4]]),
([4,2], [[4,2],[1,5],[5,2],[5,3],[2,4]]),
([5, 2], [[4,2],[1,5],[5,2],[4,3],[4,1]])
]
for output, input in data:
res = findRedundantDirectedConnection(input)
if res != output:
raise f'expect {output} found {res}'
findRedundantDirectedConnection([[2,3],[3,1],[3,4],[4,2]])
解②： 并查集1+反引用表
思路
使用并查集辅助是一个更普遍的，更规整化的思路，但对于有向树来说，单靠并查集也不能直接找到环，而并查集的路径压缩也会干扰对双头节点的判断，因此我们还需要一个单独的反向引用的表来维护直接父节点的信息。
除此之外，我们通过一个巧妙的构思，可以 One Pass 地求出需要的双头节点和环的信息：
-
只需要当发现双头节点的时候，跳过去，不进行 Union ，相当于删除双头节点2的两条边里顺序靠后的那一条，在这种情况下如果仍然发现有一条边的两个点在并查集里有一样的根，那么这条边就是环上的一条边，而且是环上顺序最后的一条边3；
-
这样当我们通过反引用表找到了双头节点，并通过反引用表与并查集的配合找到了环上最后的边的时候，甚至可以提前退出循环，都不需要读完全部的边
根据双头节点和环的信息最后输出：
- 没发现双头节点。那必然只有环，直接输出环上最后一条边即可；
- 没发现环。可能有两种，都是输出我们保存的双头节点顺序靠后的边即可：
- 有一个环，但是也是双头节点顺序靠后的一条边，因为跳过，所以没发现
- 根本没有环
- 有双头节点但也发现了环。这说明双头节点顺序靠后的边不在环上，因此我们从反引用表里就可以得到双头节点在环上的边。
Rust 实现
/// improved edition after read other solutions
pub fn resolve_better(edges: Vec<Vec<i32>>) -> Vec<i32> {
struct Aux {
ds: Vec<i32>,
p: Vec<i32>
}
impl Aux {
fn new(cap: usize) -> Self {
Self {
ds: vec![0; cap],
p: vec![0; cap]
}
}
fn find(&mut self, v: i32) -> i32 {
let p = self.ds[v as usize];
if p == 0 {
v
}
else {
self.ds[v as usize] = self.find(p);
self.ds[v as usize]
}
}
/// Ignore rank/height compare to save space as we have compressed the path.
#[inline(always)]
fn union(&mut self, u: i32, v: i32) -> Result<(), ()> {
let u_root = self.find(u);
let v_root = self.find(v);
if u_root == v_root {
return Err(());
}
self.ds[v_root as usize] = u_root;
Ok(())
}
#[inline(always)]
fn direct_find(&self, v: i32) -> i32 {
self.p[v as usize]
}
#[inline(always)]
fn direct_union(&mut self, u: i32, v: i32) {
self.p[v as usize] = u;
}
}
let mut aux = Aux::new(edges.len() + 1);
let mut double_head_cand = None;
let mut cycle_cand = None;
for e in edges.iter() {
let u = e[0];
let v = e[1];
// found double head
if aux.direct_find(v) != 0 {
double_head_cand = Some((u, v));
continue;
}
aux.direct_union(u, v);
// found cycle (double head case has been excluded)
if aux.union(u, v).is_err() {
cycle_cand = Some((u, v));
}
if double_head_cand.is_some() && cycle_cand.is_some() { break }
}
if double_head_cand.is_none() {
if let Some((u, v)) = cycle_cand {
return vec![u, v];
}
}
// 1. the last double head edge cover the cycle edge.
// 2. no cycle edge.
else if cycle_cand.is_none() {
if let Some((u, v)) = double_head_cand {
return vec![u, v];
}
}
else {
if let Some((_u, v)) = double_head_cand {
return vec![aux.direct_find(v), v];
}
}
unreachable!()
}
fn main() {
let sample = vec![
(vec![[1, 2], [1, 3], [2, 3]], [2, 3]),
(vec![[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]], [4, 1]),
(vec![[2,1],[3,1],[4,2],[1,4]], [2, 1]),
(vec![[1,2],[2,1],[2,3],[3,4]], [2, 1])
];
let norm_sample = Vec::from_iter(sample
.into_iter()
.map(|(input, expect)|
(
input
.into_iter()
.map(|arr| Vec::from_iter(arr.into_iter()))
.collect::<Vec<Vec<i32>>>(),
Vec::from_iter(
expect
.into_iter()
)
)
));
for (edges, expect) in norm_sample {
assert_eq!(resolve_better(edges.clone()), expect,);
}
}
这里对并查集的维护没有根据树的大小或者树高来选择合并的顺序，这主要是考虑到路径压缩已经足够优化，按照经验，再维护并查集树的平衡未必有明显的好处，相比花费额外的 $O(\text{n})$ 的空间4 ，并不值当。
注解
