Check if we can visit all other nodes from any node in given Directed Graph
Given N nodes, where each of them is numbered from 0 to N – 1, and array edges, where there is a directed edge from edges[i][0] to edges[i][1], the task is to find whether we can travel from any node to all other nodes or not.
Examples:
Input: N = 2, edges[] = {{0, 1}, {1, 0}};
Output: True
Explanation: We can go to node 0 from 1 and node 1 from 0Input: N = 3, edges[] = {{1, 0}};
Output: False
An approach using Kosaraju’s algorithm:
An idea of solving this problem is to think in terms of finding strongly connected component (SCC) for directed graph, We know that a directed graph is strongly connected if there is a path between all pairs of vertices.
So if there is only a single SCC then only we can visit all the nodes from any other node. The number of SCC can be found using Kosaraju’s algorithm.
Follow the steps below to implement the above idea:
- Create adjacency list adj1 for storing the graph.
- Do DFS in random order of vertices and store the visited vertices in a stack stk while backtracking.
- Reverse the direction of all edges of the adj1 graph and store the newly created graph in adj2.
- Do dfs2 in order of stack and keep count of the strongly connected components in variable scc.
- Check the count of scc:
- If the count of scc is greater than 1, return false.
- Otherwise, return true.
Below is the implementation of the above approach:
C++
// C++ code to implement above approach #include <bits/stdc++.h> using namespace std; // Function to find components void randomOrderDfs( int i, vector<vector< int > >& adj, vector< bool >& visited, stack< int >& stk) { visited[i] = true ; for ( auto child : adj[i]) { if (visited[child] == false ) { randomOrderDfs(child, adj, visited, stk); } } stk.push(i); } // Function to traverse in the reversed graph void dfs2( int i, vector<vector< int > >& adj, vector< bool >& visited) { visited[i] = true ; for ( auto child : adj[i]) { if (visited[child] == false ) { dfs2(child, adj, visited); } } } // Function to check if it is possible // to reach all other nodes from any node bool isTourPossible( int n, vector<vector< int > >& roads) { // adj1 stores adjacency matrix of // original graph adj2 stores // adjacency matrix of original graph // by reversing direction of all edges vector<vector< int > > adj1(n), adj2(n); // Create graph for ( auto i : roads) { adj1[i[0]].push_back(i[1]); } vector< bool > visited1(n, false ), visited2(n, false ); stack< int > stk; // Random dfs and maintain stack // at backtracking (endpoint) for ( int i = 0; i < n; i++) { if (visited1[i] == false ) { randomOrderDfs(i, adj1, visited1, stk); } } // Reverse all the edges for ( int i = 0; i < n; i++) { for ( auto child : adj1[i]) { adj2[child].push_back(i); } } // scc for counting the number of // strongly connected component int scc = 0; // Make second dfs at order of stk while (stk.size() > 0) { int node = stk.top(); if (visited2[node]) { stk.pop(); } else { dfs2(node, adj2, visited2); stk.pop(); scc++; if (scc > 1) return false ; } } return true ; } // Driver code int main() { int N = 2; vector<vector< int > > edges = { { 0, 1 }, { 1, 0 } }; // Function call bool result = isTourPossible(N, edges); if (result) { cout << "True" << endl; } else { cout << "False" << endl; } return 0; } |
Java
// Java program to implement the approach import java.io.*; import java.util.*; // Function to find components class GFG { // Function to find components static void randomOrderDfs( int i, ArrayList<ArrayList<Integer> > adj, boolean [] visited, Stack<Integer> stk) { visited[i] = true ; for ( int j = 0 ; j < adj.get(i).size(); j++) { int child = adj.get(i).get(j); if (visited[child] == false ) { randomOrderDfs(child, adj, visited, stk); } } stk.push(i); } // Function to traverse in the reversed graph static void dfs2( int i, ArrayList<ArrayList<Integer> > adj, boolean [] visited) { visited[i] = true ; for ( int j = 0 ; j < adj.get(i).size(); j++) { int child = adj.get(j).get( 0 ); if (visited[child] == false ) { dfs2(child, adj, visited); } } } // Function to check if it is possible // to reach all other nodes from any node static boolean isTourPossible( int n, int [][] roads) { // adj1 stores adjacency matrix of // original graph adj2 stores // adjacency matrix of original graph // by reversing direction of all edges ArrayList<ArrayList<Integer> > adj1 = new ArrayList<>(); ArrayList<ArrayList<Integer> > adj2 = new ArrayList<>(); ; for ( int i = 0 ; i < n; i++) { adj1.add( new ArrayList<Integer>()); adj2.add( new ArrayList<Integer>()); } // Create graph for ( int i = 0 ; i < n; i++) { adj1.get(roads[i][ 0 ]).add(roads[i][ 1 ]); } boolean [] visited1 = new boolean [n]; boolean [] visited2 = new boolean [n]; for ( int i = 0 ; i < n; i++) { visited1[i] = false ; visited2[i] = false ; } Stack<Integer> stk = new Stack<Integer>(); // Random dfs and maintain stack // at backtracking (endpoint) for ( int i = 0 ; i < n; i++) { if (visited1[i] == false ) { randomOrderDfs(i, adj1, visited1, stk); } } // Reverse all the edges for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < adj1.get(i).size(); j++) { int child = adj1.get(i).get(j); adj2.get(child).add(i); } } // scc for counting the number of // strongly connected component int scc = 0 ; // Make second dfs at order of stk while (stk.size() > 0 ) { int node = stk.peek(); if (visited2[node]) { stk.pop(); } else { dfs2(node, adj2, visited2); stk.pop(); scc++; if (scc > 1 ) return false ; } } return true ; } // Driver code public static void main(String[] args) { int N = 2 ; int edges[][] = { { 0 , 1 }, { 1 , 0 } }; // Function call boolean result = isTourPossible(N, edges); if (result) { System.out.println( "True" ); } else { System.out.println( "False" ); } } } // This code is contributed by garg28harsh. |
Python3
# Python code to implement above approach # Function to find components def randomOrderDfs(i, adj, visited, stk): visited[i] = True for child in adj[i]: if (visited[child] = = False ): randomOrderDfs(child, adj, visited, stk) stk.append(i) # Function to traverse in the reversed graph def dfs2(i, adj, visited): visited[i] = True for child in adj[i]: if (visited[child] = = False ): dfs2(child, adj, visited) # Function to check if it is possible # to reach all other nodes from any node def isTourPossible(n,roads): # adj1 stores adjacency matrix of # original graph adj2 stores # adjacency matrix of original graph # by reversing direction of all edges adj1 = [[] for i in range (n)] adj2 = [[] for i in range (n)] # Create graph for i in roads: adj1[i[ 0 ]].append(i[ 1 ]) visited1 = [ False ] * n visited2 = [ False ] * n stk = [] # Random dfs and maintain stack # at backtracking (endpoint) for i in range (n): if (visited1[i] = = False ): randomOrderDfs(i,adj1,visited1,stk) # Reverse all the edges for i in range (n): for child in adj1[i]: adj2[child].append(i) # scc for counting the number of # strongly connected component scc = 0 # Make second dfs at order of stk while ( len (stk) > 0 ): node = stk[ len (stk) - 1 ] if (visited2[node]): stk.pop() else : dfs2(node,adj2,visited2) stk.pop() scc = scc + 1 if (scc> 1 ): return False return True # Driver code N = 2 edges = [[ 0 , 1 ],[ 1 , 0 ]] # Function call result = isTourPossible(N,edges) if (result): print ( "True" ) else : print ( "False" ) # This code is contributed by Pushpesh Raj. |
C#
// C# program to implement the approach using System; using System.Collections.Generic; // Function to find components class Program { // Function to find components static void RandomOrderDfs( int i, List<List< int > > adj, bool [] visited, Stack< int > stk) { visited[i] = true ; for ( int j = 0; j < adj[i].Count; j++) { int child = adj[i][j]; if (!visited[child]) { RandomOrderDfs(child, adj, visited, stk); } } stk.Push(i); } // Function to traverse in the reversed graph static void Dfs2( int i, List<List< int > > adj, bool [] visited) { visited[i] = true ; for ( int j = 0; j < adj[i].Count; j++) { int child = adj[j][0]; if (!visited[child]) { Dfs2(child, adj, visited); } } } // Function to check if it is possible // to reach all other nodes from any node static bool IsTourPossible( int n, int [][] roads) { // adj1 stores adjacency matrix of // original graph adj2 stores // adjacency matrix of original graph // by reversing direction of all edges List<List< int > > adj1 = new List<List< int > >(); List<List< int > > adj2 = new List<List< int > >(); for ( int i = 0; i < n; i++) { adj1.Add( new List< int >()); adj2.Add( new List< int >()); } for ( int i = 0; i < n; i++) { adj1[roads[i][0]].Add(roads[i][1]); } bool [] visited1 = new bool [n]; bool [] visited2 = new bool [n]; for ( int i = 0; i < n; i++) { visited1[i] = false ; visited2[i] = false ; } Stack< int > stk = new Stack< int >(); // Random dfs and maintain stack // at backtracking (endpoint) for ( int i = 0; i < n; i++) { if (!visited1[i]) { RandomOrderDfs(i, adj1, visited1, stk); } } // Reverse all the edges for ( int i = 0; i < n; i++) { for ( int j = 0; j < adj1[i].Count; j++) { int child = adj1[i][j]; adj2[child].Add(i); } } int scc = 0; while (stk.Count > 0) { int node = stk.Peek(); if (visited2[node]) { stk.Pop(); } else { Dfs2(node, adj2, visited2); stk.Pop(); scc++; if (scc > 1) { return false ; } } } return true ; } // Driver code static void Main( string [] args) { int N = 2; int [][] edges = new int [][] { new int [] { 0, 1 }, new int [] { 1, 0 } }; bool result = IsTourPossible(N, edges); Console.WriteLine(result ? "True" : "False" ); } } |
Javascript
// JavaScript code to implement above approach function randomOrderDfs(i, adj, visited, stk) { visited[i] = true ; for (let child of adj[i]) { if (!visited[child]) { randomOrderDfs(child, adj, visited, stk); } } stk.push(i); } function dfs2(i, adj, visited) { visited[i] = true ; for (let child of adj[i]) { if (!visited[child]) { dfs2(child, adj, visited); } } } function isTourPossible(n, roads) { // adj1 stores adjacency matrix of // original graph adj2 stores // adjacency matrix of original graph // by reversing direction of all edges let adj1 = new Array(n), adj2 = new Array(n); for (let i = 0; i < n; i++) { adj1[i] = []; adj2[i] = []; } // Create graph for (let i of roads) { adj1[i[0]].push(i[1]); } let visited1 = new Array(n).fill( false ), visited2 = new Array(n).fill( false ); let stk = []; // Random dfs and maintain stack // at backtracking (endpoint) for (let i = 0; i < n; i++) { if (!visited1[i]) { randomOrderDfs(i, adj1, visited1, stk); } } // Reverse all the edges for (let i = 0; i < n; i++) { for (let child of adj1[i]) { adj2[child].push(i); } } // scc for counting the number of // strongly connected component let scc = 0; // Make second dfs at order of stk while (stk.length > 0) { let node = stk.pop(); if (!visited2[node]) { dfs2(node, adj2, visited2); scc++; if (scc > 1) return false ; } } return true ; } let N = 2; let edges = [ [0, 1], [1, 0] ]; // Function call let result = isTourPossible(N, edges); if (result) { console.log( "True" ); } else { console.log( "False" ); } // this code is contributed by dany |
True
Time Complexity: O(N+E), where E is the number of edges
Auxiliary Space: O(N+E)