We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Redundant Connection II

Difficulty: Hard

Problem Description

In this problem, a rooted tree is a directed graph such that there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents. The given input is a directed graph that started as a rooted tree with n nodes (with distinct values from 1 to n), with one additional directed edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u_i, v_i] that represents a directed edge connecting nodes u_i and v_i, where u_i is a parent of child v_i. Return an edge that can be removed so that the resulting graph is a rooted tree of n nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

Key Insights

  • The graph is originally a rooted tree with one additional edge.
  • The added edge creates a cycle or an additional connection that violates the tree structure.
  • To identify which edge to remove, we need to determine which edge introduces the cycle.
  • The edge to be removed must be such that removing it restores the tree properties.

Space and Time Complexity

Time Complexity: O(n) – we traverse the edges to find the cycle and validate the tree structure. Space Complexity: O(n) – we use data structures to keep track of visited nodes and the parent-child relationships.

Solution

To solve this problem, we can use a Union-Find (Disjoint Set Union) data structure to detect cycles in the directed graph. The main steps include:

  1. Initialize a Union-Find structure to manage the connectivity of nodes.
  2. Iterate through each edge and attempt to union the two nodes.
  3. If a union operation fails (indicating a cycle), we keep track of this edge as a candidate for removal.
  4. After processing all edges, we need to check if the graph can form a tree by ensuring there is exactly one root and all nodes can be connected.
  5. Finally, return the last edge that might be removed to restore the tree structure.

Code Solutions

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size + 1))
        self.rank = [1] * (size + 1)

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        rootU = self.find(u)
        rootV = self.find(v)
        if rootU == rootV:
            return False
        if self.rank[rootU] > self.rank[rootV]:
            self.parent[rootV] = rootU
        elif self.rank[rootU] < self.rank[rootV]:
            self.parent[rootU] = rootV
        else:
            self.parent[rootV] = rootU
            self.rank[rootU] += 1
        return True

def findRedundantDirectedConnection(edges):
    n = len(edges)
    uf = UnionFind(n)
    candidate1 = candidate2 = None

    for u, v in edges:
        if uf.find(v) != v:  # v already has a parent
            candidate1 = (uf.find(v), v)  # the edge that creates a cycle
            candidate2 = (u, v)  # the edge to check for removal
            continue
        if not uf.union(u, v):
            candidate1 = (u, v)  # cycle detected

    if not candidate1:
        return []

    uf = UnionFind(n)
    for u, v in edges:
        if (u, v) == candidate1:
            continue
        if not uf.union(u, v):
            return candidate1
    return candidate2
← Back to All Questions