冗余连接 II

685. 冗余连接 II

在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。每个元素是一对 [u_i, v_i]，用以表示有向图中连接顶点 u_i 和顶点 v_i 的边，其中 u_i 是 v_i 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例 1：

输入：edges = [[1,2],[1,3],[2,3]]
输出：[2,3]

示例 2：

输入：edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出：[4,1]

提示：

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= u_i, v_i <= n

相似题目

冗余连接

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) { } };

rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2024-10-28 09:26:39

impl Solution {
    pub fn find_redundant_directed_connection(edges: Vec<Vec<i32>>) -> Vec<i32> {
        let N = edges.len();
        let mut father:Vec<i32> = Vec::with_capacity(N+1);
        let mut unionset:Vec<usize> = Vec::with_capacity(N+1);

        let mut triangle:Option<(i32, i32, i32)> = None;
        let mut cycle:Option<(i32, i32)> = None;

        for i in 0..=N {
            father.push(i as i32);
            unionset.push(i);
        }
        for e in edges.iter() {
            let r  = e[0];
            let t  = e[1];
            let ru = r as usize;
            let tu = t as usize;

            if father[ tu ] != t { triangle = Some( (father[tu], r, t) );
            } else {
                father[ tu ] = r;

                let mut rx = ru;
                let mut tx = tu;
                while unionset[rx] != rx { rx = unionset[rx]; }
                while unionset[tx] != tx { tx = unionset[tx]; }

                if rx == tx {
                    cycle = Some( (r,t) );
                } else {
                    unionset[tx] = rx;
                }
            }
        }
        return if let Some( (a,b,c) ) = triangle {
            if let Some(_) = cycle { vec![ a,c ] } else { vec![ b,c ] }
        } else {
            if let Some( (r,t) ) = cycle { vec![ r,t ] } else { panic!() } 
        }

    }
}

java 解法, 执行用时: 1 ms, 内存消耗: 42.5 MB, 提交时间: 2023-10-10 14:41:04

class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n + 1);
        int[] parent = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
        }
        int conflict = -1;
        int cycle = -1;
        for (int i = 0; i < n; ++i) {
            int[] edge = edges[i];
            int node1 = edge[0], node2 = edge[1];
            if (parent[node2] != node2) {
                conflict = i;
            } else {
                parent[node2] = node1;
                if (uf.find(node1) == uf.find(node2)) {
                    cycle = i;
                } else {
                    uf.union(node1, node2);
                }
            }
        }
        if (conflict < 0) {
            int[] redundant = {edges[cycle][0], edges[cycle][1]};
            return redundant;
        } else {
            int[] conflictEdge = edges[conflict];
            if (cycle >= 0) {
                int[] redundant = {parent[conflictEdge[1]], conflictEdge[1]};
                return redundant;
            } else {
                int[] redundant = {conflictEdge[0], conflictEdge[1]};
                return redundant;
            }
        }
    }
}

class UnionFind {
    int[] ancestor;

    public UnionFind(int n) {
        ancestor = new int[n];
        for (int i = 0; i < n; ++i) {
            ancestor[i] = i;
        }
    }

    public void union(int index1, int index2) {
        ancestor[find(index1)] = find(index2);
    }

    public int find(int index) {
        if (ancestor[index] != index) {
            ancestor[index] = find(ancestor[index]);
        }
        return ancestor[index];
    }
}

cpp 解法, 执行用时: 8 ms, 内存消耗: 10.1 MB, 提交时间: 2023-10-10 14:40:45

struct UnionFind {
    vector <int> ancestor;

    UnionFind(int n) {
        ancestor.resize(n);
        for (int i = 0; i < n; ++i) {
            ancestor[i] = i;
        }
    }

    int find(int index) {
        return index == ancestor[index] ? index : ancestor[index] = find(ancestor[index]);
    }

    void merge(int u, int v) {
        ancestor[find(u)] = find(v);
    }
};

class Solution {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        UnionFind uf = UnionFind(n + 1);
        auto parent = vector<int>(n + 1);
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
        }
        int conflict = -1;
        int cycle = -1;
        for (int i = 0; i < n; ++i) {
            auto edge = edges[i];
            int node1 = edge[0], node2 = edge[1];
            if (parent[node2] != node2) {
                conflict = i;
            } else {
                parent[node2] = node1;
                if (uf.find(node1) == uf.find(node2)) {
                    cycle = i;
                } else {
                    uf.merge(node1, node2);
                }
            }
        }
        if (conflict < 0) {
            auto redundant = vector<int> {edges[cycle][0], edges[cycle][1]};
            return redundant;
        } else {
            auto conflictEdge = edges[conflict];
            if (cycle >= 0) {
                auto redundant = vector<int> {parent[conflictEdge[1]], conflictEdge[1]};
                return redundant;
            } else {
                auto redundant = vector<int> {conflictEdge[0], conflictEdge[1]};
                return redundant;
            }
        }
    }
};

golang 解法, 执行用时: 4 ms, 内存消耗: 3.3 MB, 提交时间: 2023-10-10 14:40:19

func findRedundantDirectedConnection(edges [][]int) (redundantEdge []int) {
    n := len(edges)
    uf := newUnionFind(n + 1)
    parent := make([]int, n+1) // parent[i] 表示 i 的父节点
    for i := range parent {
        parent[i] = i
    }

    var conflictEdge, cycleEdge []int
    for _, edge := range edges {
        from, to := edge[0], edge[1]
        if parent[to] != to { // to 有两个父节点
            conflictEdge = edge
        } else {
            parent[to] = from
            if uf.find(from) == uf.find(to) { // from 和 to 已连接
                cycleEdge = edge
            } else {
                uf.union(from, to)
            }
        }
    }

    // 若不存在一个节点有两个父节点的情况，则附加的边一定导致环路出现
    if conflictEdge == nil {
        return cycleEdge
    }
    // conflictEdge[1] 有两个父节点，其中之一与其构成附加的边
    // 由于我们是按照 edges 的顺序连接的，若在访问到 conflictEdge 之前已经形成了环路，则附加的边在环上
    // 否则附加的边就是 conflictEdge
    if cycleEdge != nil {
        return []int{parent[conflictEdge[1]], conflictEdge[1]}
    }
    return conflictEdge
}

type unionFind struct {
    ancestor []int
}

func newUnionFind(n int) unionFind {
    ancestor := make([]int, n)
    for i := 0; i < n; i++ {
        ancestor[i] = i
    }
    return unionFind{ancestor}
}

func (uf unionFind) find(x int) int {
    if uf.ancestor[x] != x {
        uf.ancestor[x] = uf.find(uf.ancestor[x])
    }
    return uf.ancestor[x]
}

func (uf unionFind) union(from, to int) {
    uf.ancestor[uf.find(from)] = uf.find(to)
}

python3 解法, 执行用时: 48 ms, 内存消耗: 16.4 MB, 提交时间: 2023-10-10 14:39:27

class UnionFind:
    def __init__(self, n: int):
        self.ancestor = [i for i in range(n)]
    
    # 将index1所在的集合加入到index2的集合中
    def union(self, index1: int, index2: int):
        self.ancestor[self.find(index1)] = self.find(index2)
    
    # 找到祖先
    def find(self, index: int) -> int:
        if self.ancestor[index] != index:
            self.ancestor[index] = self.find(self.ancestor[index])
        return self.ancestor[index]

class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        
        # 辅助数组parent以及并查集初始化
        nodesCount = len(edges)
        uf = UnionFind(nodesCount + 1)
        parent = list(range(nodesCount + 1))
        
        # 冲突/环标签
        conflict = -1
        cycle = -1
        
        # 开始遍历
        for i, (node1, node2) in enumerate(edges):
            if parent[node2] != node2:          # 产生冲突（有两个父节点）
                conflict = i
            else:
                parent[node2] = node1
                if uf.find(node1) == uf.find(node2):
                    cycle = i                   # 产生环（祖先相同）
                else:
                    uf.union(node1, node2)      # 合并

        # 获取有问题的边
        if conflict < 0:                                            # 没有冲突就是环的边
            return [edges[cycle][0], edges[cycle][1]]
        else:               
            conflictEdge = edges[conflict]
            if cycle >= 0:
                return [parent[conflictEdge[1]], conflictEdge[1]]   # 环的重要性比冲突大
            else:
                return [conflictEdge[0], conflictEdge[1]]           # 无环就是冲突边

上一题

下一题

详情