Check if a directed graph is connected or not

Input:

Output: Yes
Input:

Output: No

Approach:

  1. Take two bool arrays vis1 and vis2 of size N (number of nodes of a graph) and keep false in all indexes.
  2. Start at a random vertex v of the graph G, and run a DFS(G, v).
  3. Make all visited vertices v as vis1[v] = true.
  4. Now reverse the direction of all the edges.
  5. Start DFS at the vertex which was chosen at step 2.
  6. Make all visited vertices v as vis2[v] = true.
  7. If any vertex v has vis1[v] = false and vis2[v] = false then the graph is not connected.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach using namespace std; #define N 100000 // To keep correct and reverse direction vector < int >gr1[N], gr2[N]; bool vis1[N], vis2[N]; // Function to add edges void Add_edge( int u, int v) gr1[u].push_back(v); gr2[v].push_back(u); // DFS function void dfs1( int x) vis1[x] = true ; for ( auto i : gr1[x]) // DFS function void dfs2( int x) vis2[x] = true ; for ( auto i : gr2[x]) bool Is_Connected( int n) // Call for correct direction memset (vis1, false , sizeof vis1); // Call for reverse direction memset (vis2, false , sizeof vis2); for ( int i = 1; i <= n; i++) < // If any vertex it not visited in any direction // Then graph is not connected if (!vis1[i] and !vis2[i]) return false ; // If graph is connected return true ; // Driver code Add_edge(1, 2); Add_edge(1, 3); Add_edge(2, 3); Add_edge(3, 4); // Function call if (Is_Connected(n))

Java

// Java implementation of the approach import java.util.*; static int N = 100000 ; // To keep correct and reverse direction @SuppressWarnings ( "unchecked" ) static Vector[] gr1 = new Vector[N]; @SuppressWarnings ( "unchecked" ) static Vector[] gr2 = new Vector[N]; static boolean [] vis1 = new boolean [N]; static boolean [] vis2 = new boolean [N]; for ( int i = 0 ; i < N; i++) gr1[i] = new Vector<>(); gr2[i] = new Vector<>(); // Function to add edges static void Add_edge( int u, int v) // DFS function static void dfs1( int x) vis1[x] = true ; for ( int i : gr1[x]) // DFS function static void dfs2( int x) vis2[x] = true ; for ( int i : gr2[x]) static boolean Is_connected( int n) // Call for correct direction Arrays.fill(vis1, false ); // Call for reverse direction Arrays.fill(vis2, false ); for ( int i = 1 ; i <= n; i++) // If any vertex it not visited in any direction // Then graph is not connected if (!vis1[i] && !vis2[i]) return false ; // If graph is connected return true ; // Driver Code public static void main(String[] args) Add_edge( 1 , 2 ); Add_edge( 1 , 3 ); Add_edge( 2 , 3 ); Add_edge( 3 , 4 ); // Function call if (Is_connected(n)) System.out.println( "Yes" ); System.out.println( "No" ); // This code is contributed by // sanjeev2552

Python3

# Python3 implementation of the approach # To keep correct and reverse direction vis1 = [ 0 ] * N; vis2 = [ 0 ] * N; # Function to add edges def Add_edge(u, v) : if u not in gr1 : if v not in gr2 : gr1[u].append(v); gr2[v].append(u); # DFS function vis1[x] = True ; if x not in gr1 : for i in gr1[x] : if ( not vis1[i]) : # DFS function vis2[x] = True ; if x not in gr2 : for i in gr2[x] : if ( not vis2[i]) : def Is_Connected(n) : global vis1; global vis2; # Call for correct direction vis1 = [ False ] * len (vis1); # Call for reverse direction vis2 = [ False ] * len (vis2); for i in range ( 1 , n + 1 ) : # If any vertex it not visited in any direction # Then graph is not connected if ( not vis1[i] and not vis2[i]) : return False ; # If graph is connected return True ; # Driver code if __name__ = = "__main__" : Add_edge( 1 , 2 ); Add_edge( 1 , 3 ); Add_edge( 2 , 3 ); Add_edge( 3 , 4 ); # Function call if (Is_Connected(n)) : print ( "Yes" ); # This code is contributed by AnkitRai01

C#

// C# implementation of the approach using System; using System.Collections.Generic; static int N = 100000; // To keep correct and reverse direction static List< int >[] gr1 = new List< int >[N]; static List< int >[] gr2 = new List< int >[N]; static bool [] vis1 = new bool [N]; static bool [] vis2 = new bool [N]; // Function to add edges static void Add_edge( int u, int v) // DFS function static void dfs1( int x) vis1[x] = true ; foreach ( int i in gr1[x]) // DFS function static void dfs2( int x) vis2[x] = true ; foreach ( int i in gr2[x]) static bool Is_connected( int n) // Call for correct direction for ( int i = 0; i < n; i++) vis1[i] = false ; // Call for reverse direction for ( int i = 0; i < n; i++) vis2[i] = false ; for ( int i = 1; i <= n; i++) // If any vertex it not visited in any direction // Then graph is not connected if (!vis1[i] && !vis2[i]) return false ; // If graph is connected return true ; // Driver Code public static void Main(String[] args) for ( int i = 0; i < N; i++) gr1[i] = new List< int >(); gr2[i] = new List< int >(); Add_edge(1, 2); Add_edge(1, 3); Add_edge(2, 3); Add_edge(3, 4); // Function call if (Is_connected(n)) Console.WriteLine( "Yes" ); Console.WriteLine( "No" ); // This code is contributed by PrinciRaj1992

Javascript

// Javascript implementation of the approach let N = 100000; // To keep correct and reverse direction for (let i = 0; i < N; i++) let vis1 = new Array(N); let vis2 = new Array(N); vis1.fill( false ); vis2.fill( false ); // Function to add edges function Add_edge(u, v) // DFS function function dfs1(x) vis1[x] = true ; for (let i = 0; i < gr1[x].length; i++) if (!vis1[gr1[x][i]]) // DFS function function dfs2(x) vis2[x] = true ; for (let i = 0; i < gr2[x].length; i++) if (!vis2[gr2[x][i]]) function Is_connected(n) // Call for correct direction for (let i = 0; i < n; i++) vis1[i] = false ; // Call for reverse direction for (let i = 0; i < n; i++) vis2[i] = false ; for (let i = 1; i <= n; i++) // If any vertex it not visited in any direction // Then graph is not connected if (!vis1[i] && !vis2[i]) return false ; // If graph is connected return true ; for (let i = 0; i < N; i++) Add_edge(1, 2); Add_edge(1, 3); Add_edge(2, 3); Add_edge(3, 4); // Function call if (Is_connected(n)) document.write( "Yes" ); document.write( "No" ); // This code is contributed by divyesh072019. Output:

Time Complexity: O(V+E) where V is the number of vertices and E is the number of edges.

Auxiliary Space: O(B^M), where B is the maximum branching factor of the search tree and M is the maximum depth of the state space.

Like Article -->

Please Login to comment.

Similar Reads

Convert undirected connected graph to strongly connected directed graph

Given an undirected graph of N vertices and M edges, the task is to assign directions to the given M Edges such that the graph becomes Strongly Connected Components. If a graph cannot be converted into Strongly Connected Components then print "-1". Examples: Input: N = 5, Edges[][] = < < 0, 1 >, < 0, 2 >, < 1, 2 >, < 1, 4 >, < 2, 3 >, < 3, 4 >> Ou

14 min read What is Directed Graph? | Directed Graph meaning

A directed graph is defined as a type of graph where the edges have a direction associated with them. Characteristics of Directed Graph Directed graphs have several characteristics that make them different from undirected graphs. Here are some key characteristics of directed graphs: Directed edges: In a directed graph, edges have a direction associ

3 min read Check if a given directed graph is strongly connected | Set 2 (Kosaraju using BFS)

Given a directed graph, find out whether the graph is strongly connected or not. A directed graph is strongly connected if there is a path between any two pairs of vertices. There are different methods to check the connectivity of directed graph but one of the optimized method is Kosaraju’s DFS based simple algorithm. Kosaraju’s BFS based simple al

14 min read Find Weakly Connected Components in a Directed Graph

Weakly Connected Graph: A directed graph 'G = (V, E)' is weakly connected if the underlying undirected graph Ĝ is connected. The underlying undirected graph is the graph Ĝ = (V, Ê) where Ê represents the set of undirected edges that is obtained by removing the arrowheads from the directed edges and making them bidirectional in G. Example: The direc

9 min read Minimum edges required to make a Directed Graph Strongly Connected

Given a Directed graph of N vertices and M edges, the task is to find the minimum number of edges required to make the given graph Strongly Connected. Examples: Input: N = 3, M = 3, source[] = <1, 2, 1>, destination[] = Output: 1 Explanation: Adding a directed edge joining the pair of vertices makes the graph strongly connected. H

10 min read

Connect a graph by M edges such that the graph does not contain any cycle and Bitwise AND of connected vertices is maximum

Given an array arr[] consisting of values of N vertices of an initially unconnected Graph and an integer M, the task is to connect some vertices of the graph with exactly M edges, forming only one connected component, such that no cycle can be formed and Bitwise AND of the connected vertices is maximum possible. Examples: Input: arr[] = 9 min read Check if incoming edges in a vertex of directed graph is equal to vertex itself or not

Given a directed Graph G(V, E) with V vertices and E edges, the task is to check that for all vertices of the given graph, the incoming edges in a vertex is equal to the vertex itself or not. Examples: Input: Output: Yes Explanation: For vertex 0 there are 0 incoming edges, for vertex 1 there is 1 incoming edge. Same for vertex 2 nd 3. Approach: Th

6 min read Check if a given Graph is 2-edge connected or not

Given an undirected graph G, with V vertices and E edges, the task is to check whether the graph is 2-edge connected or not. A graph is said to be 2-edge connected if, on removing any edge of the graph, it still remains connected, i.e. it contains no Bridges. Examples: Input: V = 7, E = 9 Output: Yes Explanation: Given any vertex in the graph, we c

12 min read Check if given graph is connected or not after removal of ith node sequential

Given an undirected graph with N nodes, M edges given by array edges[][2] and permutation array A[] of size N which indicates the order in which each and every node of graph will be removed. The task is to find if graph is connected or not after removal of ith node sequential from given array A[]. Graph is connected if it is possible to traverse fr

15 min read Convert the undirected graph into directed graph such that there is no path of length greater than 1

Given an undirected graph with N vertices and M edges and no self loops or multiple edges. The task is to convert the given undirected graph into a directed graph such that there is no path of length greater than 1. If it is possible to make such a graph then print two space-separated integers u and v in M lines where u, v denotes source and destin

10 min read Print Nodes which are not part of any cycle in a Directed Graph

Given a directed graph G N nodes and E Edges consisting of nodes valued [0, N – 1] and a 2D array Edges[][2] of type that denotes a directed edge between vertices u and v. The task is to find the nodes that are not part of any cycle in the given graph G. Examples: Input: N = 4, E = 4, Edges[][2] = < , , , >Output: 1E

14 min read 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>, >;Output: TrueExplanation: We can go to node 0 from 1 and node 1 from 0 In 10 min read Check if a graph is strongly connected | Set 1 (Kosaraju using DFS)

Given a directed graph, find out whether the graph is strongly connected or not. A directed graph is strongly connected if there is a path between any two pair of vertices. For example, following is a strongly connected graph. It is easy for undirected graph, we can just do a BFS and DFS starting from any vertex. If BFS or DFS visits all vertices,

13 min read Check if there exists a connected graph that satisfies the given conditions

Given two integers N and K. The task is to find a connected graph with N vertices such that there are exactly K pairs (i, j) where the shortest distance between them is 2. If no such graph exists then print -1. Note: The first-line output should be the number of edges(say m) in the graph and the next m lines should contain two numbers represents th

7 min read Check if longest connected component forms a palindrome in undirected graph

Given an undirected graph with V vertices and E edges, the task is to check that if the largest connected component of the graph forms a palindrome in the undirected graph. Examples: Input: Output: Longest connected component is Palindrome Explanation: Longest connected component is <5, 15, 5>which forms an palindrome by values. Input: Output: Lon

15+ min read Queries to check if vertices X and Y are in the same Connected Component of an Undirected Graph

Given an undirected graph consisting of N vertices and M edges and queries Q[][] of the type , the task is to check if the vertices X and Y are in the same connected component of the Graph. Examples: Input: Q[][] = , , > Graph: 1-3-4 2 | 5 Output: Yes No No Explanation: From the given graph, it can be observed that the vert

11 min read Check if every vertex triplet in graph contains two vertices connected to third vertex

Given an undirected graph with N vertices and K edges, the task is to check if for every combination of three vertices in the graph, there exists two vertices which are connected to third vertex. In other words, for every vertex triplet (a, b, c), if there exists a path between a and c, then there should also exist a path between b and c. Examples:

9 min read Find if there is a path between two vertices in a directed graph

Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second. Example: Consider the following Graph: Input : (u, v) = (1, 3) Output: Yes Explanation: There is a path from 1 to 3, 1 -> 2 -> 3 Input : (u, v) = (3, 6) Output: No Explanation: There is no path from 3 to 6 Approach: Either Bread

15 min read Shortest path with exactly k edges in a directed and weighted graph

Given a directed and two vertices ‘u’ and ‘v’ in it, find shortest path from ‘u’ to ‘v’ with exactly k edges on the path. The graph is given as adjacency matrix representation where value of graph[i][j] indicates the weight of an edge from vertex i to vertex j and a value INF(infinite) indicates no edge from i to j. For example, consider the follow

15+ min read Assign directions to edges so that the directed graph remains acyclic

Given a graph with both directed and undirected edges. It is given that the directed edges don't form cycle. How to assign directions to undirected edges so that the graph (with all directed edges) remains acyclic even after the assignment? For example, in the below graph, blue edges don't have directions. We strongly recommend to minimize your bro

1 min read Number of shortest paths in an unweighted and directed graph

Given an unweighted directed graph, can be cyclic or acyclic. Print the number of shortest paths from a given vertex to each of the vertices. For example consider the below graph. There is one shortest path vertex 0 to vertex 0 (from each vertex there is a single shortest path to itself), one shortest path between vertex 0 to vertex 2 (0->2), an

11 min read Find if there is a path between two vertices in a directed graph | Set 2

Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second. Example: Consider the following Graph: Input : (u, v) = (1, 3) Output: Yes Explanation: There is a path from 1 to 3, 1 -> 2 -> 3 Input : (u, v) = (3, 6) Output: No Explanation: There is no path from 3 to 6 A BFS or DFS based sol

7 min read Number of paths from source to destination in a directed acyclic graph

Given a Directed Acyclic Graph with n vertices and m edges. The task is to find the number of different paths that exist from a source vertex to destination vertex. Examples: Input: source = 0, destination = 4 Output: 3 Explanation: 0 -> 2 -> 3 -> 4 0 -> 3 -> 4 0 -> 4 Input: source = 0, destination = 1 Output: 1 Explanation: There

15+ min read Minimum edges to be added in a directed graph so that any node can be reachable from a given node

Given a directed graph and a node X. The task is to find the minimum number of edges that must be added to the graph such that any node can be reachable from the given node.Examples: Input: X = 0 Output: 3Input: X = 4 Output: 1 Approach: First, let's mark all the vertices reachable from X as good, using a simple DFS. Then, for each bad vertex (vert

10 min read Longest path in a directed Acyclic graph | Dynamic Programming

Given a directed graph G with N vertices and M edges. The task is to find the length of the longest directed path in Graph.Note: Length of a directed path is the number of edges in it. Examples: Input: N = 4, M = 5 Output: 3 The directed path 1->3->2->4 Input: N = 5, M = 8 Output: 3 Simple Approach: A naive approach is to calculate the len

8 min read Convert Directed Graph into a Tree

Given an array arr[] of size N. There is an edge from i to arr[i]. The task is to convert this directed graph into tree by changing some of the edges. If for some i, arr[i] = i then i represents the root of the tree. In case of multiple answers print any of them.Examples: Input: arr[] = <6, 6, 0, 1, 4, 3, 3, 4, 0>Output: <6, 6, 0, 1, 4, 3, 4, 4, 0

9 min read Count all Hamiltonian paths in a given directed graph

Given a directed graph of N vertices valued from 0 to N - 1 and array graph[] of size K represents the Adjacency List of the given graph, the task is to count all Hamiltonian Paths in it which start at the 0th vertex and end at the (N - 1)th vertex. Note: Hamiltonian path is defined as the path which visits every vertex of the graph exactly once. E

9 min read Find the number of paths of length K in a directed graph

Given a directed, unweighted graph with N vertices and an integer K. The task is to find the number of paths of length K for each pair of vertices (u, v). Paths don't have to be simple i.e. vertices and edges can be visited any number of times in a single path. The graph is represented as adjacency matrix where the value G[i][j] = 1 indicates that

9 min read Shortest path with exactly k edges in a directed and weighted graph | Set 2

Given a directed weighted graph and two vertices S and D in it, the task is to find the shortest path from S to D with exactly K edges on the path. If no such path exists, print -1. Examples: Input: N = 3, K = 2, ed = <<<1, 2>, 5>, , 3>, , 4>>, S = 1, D = 3 Output: 8 Explanation: The shortest path with two edges will be 1->2->3 8 min read Why Prim’s and Kruskal's MST algorithm fails for Directed Graph?

Pre-requisites: Graph and its representations Greedy Algorithms | Set 5 (Prim’s Minimum Spanning Tree (MST)) Kruskal’s Minimum Spanning Tree Algorithm | Greedy Algo-2 Given a directed graph D = < V, E >, the task is to find the minimum spanning tree for the given directed graph Example: But the Prim's Minimum Spanning Tree and Kruskal's algor