Vultr DocsLatest Content

Redundant Connection II

Updated on 07 July, 2025
Redundant Connection II header image

Problem Statement

In this scenario, we are provided with a directed graph which initially formed a rooted tree with n distinct nodes numbered from 1 to n. A rooted tree is characterized by having one node as the root, which has no parents, while all other nodes have exactly one parent that links back to the root in a directed manner. However, this initial structure was altered by the addition of one extra directed edge connecting two different nodes.

This modification results in a graph represented as a 2D array, edges, where each entry [ui, vi] indicates a directed edge where node ui is the parent of node vi. The task is to identify and return an edge that, when removed, will revert the structure back to being a rooted tree of n nodes. If multiple solutions exist, we should return the edge that appears last in the array.

Examples

Example 1

Input:

edges = [[1,2],[1,3],[2,3]]

Output:

[2,3]

Example 2

Input:

edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]

Output:

[4,1]

Constraints

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • ui != vi

Approach and Intuition

To solve the problem of restoring the directed graph back to a rooted tree, follow these steps based on the given examples and constraints:

  1. Identify Cycle or Extra Parent:

    • The addition of an extra edge in a rooted tree could either create a cycle or make a node have two parents. We aim to identify this anomaly.

  2. Checking Each Edge's Impact:

    • To determine if an edge [ui, vi] is the extra one, temporarily remove it and check if the graph still has any nodes with two parents or any cycles. If no such anomalies exist, this edge is a likely candidate.

  3. Restoration of Tree Properties:

    • The rooted tree must have exactly one node without parents (the root) and all other nodes must have exactly one parent. Any violation checked in the previous step indicates the likely extra edge.

  4. Ensure Uniqueness or Order Preference:

    • Since multiple edges might be potential candidates to be removed to restore tree properties, the edge that appears last in the provided list should be selected, adhering to the constraints.

Given the constraints including 3 <= n <= 1000 and uniqueness of nodes within an edge, the detection of cycles and the identification of multiple parents are feasible within performance limits using standard graph traversal or union-find techniques.

Solutions

  • Java
java 
class Solution {
    public int[] redundantConnectionFinder(int[][] edges) {
        int edgeCount = edges.length;
        Map<Integer, Integer> edgeToParent = new HashMap<>();
        List<int[]> possibleRedundants = new ArrayList<>();
        for (int[] edge : edges) {
            if (edgeToParent.containsKey(edge[1])) {
                possibleRedundants.add(new int[]{edgeToParent.get(edge[1]), edge[1]});
                possibleRedundants.add(edge);
            } else {
                edgeToParent.put(edge[1], edge[0]);
            }
        }
    
        int startNode = findRoot(1, edgeToParent).node;
        if (possibleRedundants.isEmpty()) {
            Set<Integer> cycleMembers = findRoot(startNode, edgeToParent).visitedNodes;
            int[] redundant = new int[]{0, 0};
            for (int[] edge : edges) {
                if (cycleMembers.contains(edge[0]) && cycleMembers.contains(edge[1])) {
                    redundant = edge;
                }
            }
            return redundant;
        }
    
        Map<Integer, List<Integer>> nodeChildren = new HashMap<>();
        for (int v : edgeToParent.keySet()) {
            int parentValue = edgeToParent.get(v);
            nodeChildren.computeIfAbsent(parentValue, k -> new ArrayList<>()).add(v);
        }
    
        boolean[] visited = new boolean[edgeCount + 1];
        visited[0] = true;
        Stack<Integer> toVisit = new Stack<>();
        toVisit.add(startNode);
        while (!toVisit.isEmpty()) {
            int currentNode = toVisit.pop();
            if (!visited[currentNode]) {
                visited[currentNode] = true;
                if (nodeChildren.containsKey(currentNode)) {
                    for (int childNode : nodeChildren.get(currentNode)) {
                        toVisit.push(childNode);
                    }
                }
            }
        }
        for (boolean seenNode : visited) {
            if (!seenNode) {
                return possibleRedundants.get(0);
            }
        }
        return possibleRedundants.get(1);
    }
    
    public CycleInfo findRoot(int node, Map<Integer, Integer> edgeToParent) {
        Set<Integer> visitedNodes = new HashSet<>();
        while (edgeToParent.containsKey(node) && !visitedNodes.contains(node)) {
            visitedNodes.add(node);
            node = edgeToParent.get(node);
        }
        return new CycleInfo(node, visitedNodes);
    }
    
}
class CycleInfo {
    int node;
    Set<Integer> visitedNodes;
    CycleInfo(int nodeValue, Set<Integer> cycleNodes) {
        node = nodeValue;
        visitedNodes = cycleNodes;
    }
}

The provided Java program addresses the problem of finding a redundant connection in a directed graph. This involves determining which edge, if removed, will allow for a tree structure without any directed cycles. Let’s break down the solution summary:

  1. Initialization:

    • Start by defining the necessary data structures like Map<Integer, Integer> (edgeToParent) to store the parent node of each node, List<int[]> (possibleRedundants) to track possible redundant connections.

  2. Edge Addition Logic:

    • Traverse through the input edges. Check if an edge would introduce a redundant connection (detect a node with two parents) and store this edge in possibleRedundants. Otherwise, update edgeToParent to relate the child node to its parent.

  3. Cycle Detection:

    • If no redundant edges implying two parents are found, ensue cycle detection using a helper function findRoot to get members involved in a cycle. Out of the cycle members, the redundant edge is determined—the last contributing to the cycle.

  4. Root and Children Accumulation:

    • Establish nodeChildren map to list out children nodes for each node.

  5. Traversal Logic:

    • Perform a Depth First Search (DFS) to traverse the tree beginning from the root node. Record all nodes that are visited.

  6. Redundant Edge Determination:

    • Check if any node is not visited. The first edge within possibleRedundants that points to a non-visited node is deemed redundant. If all nodes are visited, choose the second edge listed in possibleRedundants.

  7. Auxiliary Class CycleInfo:

    • This helper class aids in passing multiple variables like the root node and visited nodes from the method findRoot, thus assisting in optimizing cycle detection and validation.

Each function and class serves a targeted role in assuring the graph is analyzed exhaustively for potential redundant connections. The choice of redundant connection is cleverly deduced based on the graph's structure and characteristics of directed cycles. The approach effectively combines graph traversal techniques with data structure manipulation.

Comments

No comments yet.