Extra Edge in a Directed Rooted Tree
Given a Directed rooted tree of N vertices and N-1 edges. But now your friend has added an extra edge in the tree. You have to find an edge that could have been added by your friend. If there are multiple such possible edge then Print any.
Examples:
Input: N=3 edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Explanation: the edge [2, 3] can be removed without disconnecting the graph.Input: N=5 edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
Output: [4,1]
Explanation: the edge [4, 1] can be removed without disconnecting the graph. Removing this edge results in a connected graph structure: 1 -> 2, 2 -> 3, 3 -> 4, 1 -> 5.
Approach: Below is the approach to solve the problem:
The approach used in this code is Union-Find, also known as Disjoint Set Union (DSU). Let’s consider that there was no extra edge in the directed graph, then in the graph there would be a root node (no parent) and all the other nodes will have only one parent. Now, adding an extra edge can lead to two cases:
- Connect a node to the root, so every node will have exactly one parent, or
- Connect other nodes such that exactly one of the nodes will have two parents
Explore both the cases to find the answer.
Steps to solve the problem:
- Check if there is a node with two parents by iterating over the edges of the graph.
- If we encounter a node with two parents, record the first edge to the node as edge1 and the second edge to the node as edge2
- Disconnect the edge2 to create a tree structure without the second parent.
- Initialize an ancestor array where each node initially points to itself.
- Iterate over the edges of the graph, for every edge:
- Find the root ancestor (pu) of the source node (u).
- If the root ancestor of the source node (pu) is the same as the target node (v), it indicates a cycle in the graph. In this case, if edge1 is empty, return the current edge as the extra edge. Else, if edge1 is not empty, return edge1 as the extra edge.
- If there’s no cycle, union the ancestors of u and v by making the ancestor of v point to the root ancestor of u.
- Finally, return edge2 as the extra edge, which was disconnected earlier to create a tree structure.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to find the root ancestor of a node with path // compression int findRoot(vector< int >& ancestor, int k) { if (ancestor[k] != k) ancestor[k] = findRoot(ancestor, ancestor[k]); return ancestor[k]; } vector< int > findRedundantDirectedConnection(vector<vector< int > >& edges) { int n = edges.size(); vector< int > ancestor(n + 1, 0), edge1, edge2; // Step 1: Check whether there is a node // with two parents for ( auto & edge : edges) { if (ancestor[edge[1]] == 0) { // Record the parent of this node ancestor[edge[1]] = edge[0]; } else { // Record the first set of edges edge1 = { ancestor[edge[1]], edge[1] }; // Record the second set of edges edge2 = edge; // Disconnect this edge to create a tree // structure edge[1] = 0; } } // Step 2: Union Find for ( int i = 1; i <= n; i++) ancestor[i] = i; for ( auto & edge : edges) { if (edge[1] == 0) continue ; int u = edge[0], v = edge[1], pu = findRoot(ancestor, u); if (pu == v) { // Return the edge if no edge1 if (edge1.empty()) return edge; // Return edge1 if available return edge1; } // Union the ancestors of u and v ancestor[v] = pu; } return edge2; } int main() { int N = 5; vector<vector< int > > edges = { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 1 }, { 1, 5 } }; vector< int > redundantEdge = findRedundantDirectedConnection(edges); cout << "The redundant directed connection is: [" << redundantEdge[0] << ", " << redundantEdge[1] << "]" << endl; return 0; } |
Java
import java.util.*; public class Main { // Function to find the root ancestor of a node with // path compression static int findRoot( int [] ancestor, int k) { if (ancestor[k] != k) ancestor[k] = findRoot(ancestor, ancestor[k]); return ancestor[k]; } static int [] findRedundantDirectedConnection( int [][] edges) { int n = edges.length; int [] ancestor = new int [n + 1 ], edge1 = new int [ 2 ], edge2 = new int [ 2 ]; // Step 1: Check whether there is a node with two // parents for ( int [] edge : edges) { if (ancestor[edge[ 1 ]] == 0 ) { // Record the parent of this node ancestor[edge[ 1 ]] = edge[ 0 ]; } else { // Record the first set of edges edge1 = new int [] { ancestor[edge[ 1 ]], edge[ 1 ] }; // Record the second set of edges edge2 = edge; // Disconnect this edge to create a tree // structure edge[ 1 ] = 0 ; } } // Step 2: Union Find for ( int i = 1 ; i <= n; i++) ancestor[i] = i; for ( int [] edge : edges) { if (edge[ 1 ] == 0 ) continue ; int u = edge[ 0 ], v = edge[ 1 ], pu = findRoot(ancestor, u); if (pu == v) { // Return the edge if no edge1 if (edge1[ 0 ] == 0 && edge1[ 1 ] == 0 ) return edge; // Return edge1 if available return edge1; } // Union the ancestors of u and v ancestor[v] = pu; } return edge2; } public static void main(String[] args) { int N = 5 ; int [][] edges = { { 1 , 2 }, { 2 , 3 }, { 3 , 4 }, { 4 , 1 }, { 1 , 5 } }; int [] redundantEdge = findRedundantDirectedConnection(edges); System.out.println( "The redundant directed connection is: [" + redundantEdge[ 0 ] + ", " + redundantEdge[ 1 ] + "]" ); } } |
Python3
# Nikunj Sonigara # Function to find the root ancestor of a node with path # compression def findRoot(ancestor, k): if ancestor[k] ! = k: ancestor[k] = findRoot(ancestor, ancestor[k]) return ancestor[k] def findRedundantDirectedConnection(edges): n = len (edges) ancestor = [ 0 ] * (n + 1 ) edge1, edge2 = [], [] # Step 1: Check whether there is a node # with two parents for edge in edges: if ancestor[edge[ 1 ]] = = 0 : # Record the parent of this node ancestor[edge[ 1 ]] = edge[ 0 ] else : # Record the first set of edges edge1 = [ancestor[edge[ 1 ]], edge[ 1 ]] # Record the second set of edges edge2 = edge # Disconnect this edge to create a tree # structure edge[ 1 ] = 0 # Step 2: Union Find for i in range ( 1 , n + 1 ): ancestor[i] = i for edge in edges: if edge[ 1 ] = = 0 : continue u, v = edge[ 0 ], edge[ 1 ] pu = findRoot(ancestor, u) if pu = = v: # Return the edge if no edge1 if not edge1: return edge # Return edge1 if available return edge1 # Union the ancestors of u and v ancestor[v] = pu return edge2 def main(): N = 5 edges = [ [ 1 , 2 ], [ 2 , 3 ], [ 3 , 4 ], [ 4 , 1 ], [ 1 , 5 ] ] redundant_edge = findRedundantDirectedConnection(edges) print ( "The redundant directed connection is:" , redundant_edge) if __name__ = = "__main__" : main() |
C#
using System; class Solution { // Function to find the root ancestor of a node with path compression static int FindRoot( int [] ancestor, int k) { if (ancestor[k] != k) { ancestor[k] = FindRoot(ancestor, ancestor[k]); } return ancestor[k]; } // Function to find the redundant directed connection in a graph static int [] FindRedundantDirectedConnection( int [][] edges) { int n = edges.Length; int [] ancestor = new int [n + 1]; int [] edge1 = new int [2]; int [] edge2 = new int [2]; // Step 1: Check whether there is a node with two parents foreach ( var edge in edges) { if (ancestor[edge[1]] == 0) { // Record the parent of this node ancestor[edge[1]] = edge[0]; } else { // Record the first set of edges edge1 = new int [] { ancestor[edge[1]], edge[1] }; // Record the second set of edges edge2 = edge; // Disconnect this edge to create a tree structure edge[1] = 0; } } // Step 2: Union Find for ( int i = 1; i <= n; i++) { ancestor[i] = i; } foreach ( var edge in edges) { if (edge[1] == 0) { continue ; } int u = edge[0], v = edge[1]; int pu = FindRoot(ancestor, u); if (pu == v) { // Return the edge if no edge1 if (edge1[0] == 0 && edge1[1] == 0) { return edge; } // Return edge1 if available return edge1; } // Union the ancestors of u and v ancestor[v] = pu; } return edge2; } static void Main() { int [][] edges = new int [][] { new int [] {1, 2}, new int [] {2, 3}, new int [] {3, 4}, new int [] {4, 1}, new int [] {1, 5} }; int [] redundantEdge = FindRedundantDirectedConnection(edges); Console.WriteLine( "The redundant directed connection is: [" + redundantEdge[0] + ", " + redundantEdge[1] + "]" ); } } |
Javascript
// Function to find the root ancestor of a node with path compression function findRoot(ancestor, k) { if (ancestor[k] !== k) ancestor[k] = findRoot(ancestor, ancestor[k]); return ancestor[k]; } function findRedundantDirectedConnection(edges) { const n = edges.length; const ancestor = new Array(n + 1).fill(0); let edge1 = [0, 0], edge2 = [0, 0]; // Step 1: Check whether there is a node with two parents for (const edge of edges) { if (ancestor[edge[1]] === 0) { // Record the parent of this node ancestor[edge[1]] = edge[0]; } else { // Record the first set of edges edge1 = [ancestor[edge[1]], edge[1]]; // Record the second set of edges edge2 = edge; // Disconnect this edge to create a tree structure edge[1] = 0; } } // Step 2: Union Find for (let i = 1; i <= n; i++) ancestor[i] = i; for (const edge of edges) { if (edge[1] === 0) continue ; const [u, v] = edge; const pu = findRoot(ancestor, u); if (pu === v) { // Return the edge if no edge1 if (edge1[0] === 0 && edge1[1] === 0) return edge; // Return edge1 if available return edge1; } // Union the ancestors of u and v ancestor[v] = pu; } return edge2; } // Main function function main() { const N = 5; const edges = [ [1, 2], [2, 3], [3, 4], [4, 1], [1, 5] ]; const redundantEdge = findRedundantDirectedConnection(edges); console.log( "The redundant directed connection is: [" + redundantEdge[0] + ", " + redundantEdge[1] + "]" ); } // Call the main function main(); |
The redundant directed connection is: [4, 1]
Time complexity: O(N), where N is the number of nodes.
Auxiliary Space: O(N)
Contact Us