# Check if directed graph is connected

Posted in  Vinay Khatri
Last updated on December 4, 2023

## Problem

Given a directed graph, check if it is connected or not.

#### Sample Input #### Sample Output

`YES`

#### Explanation

Start from 0, go to 1, and then 2; hence all the nodes of the graph are connected.

## Approach

We will use the Depth First Search algorithm to solve this problem. We will traverse the given graph and keep marking nodes as visited, and check the required conditions to check the connected component. Below is the algorithm to solve this problem:

1. Consider two boolean arrays, vis1 and vis2, both of which are set to false.
2. Begin with a random vertex in the graph and perform a Depth First Search.
3. Make the current visited node vis1[v] = true.
4. All of the edges should now be reversed in the direction.
5. Begin Depth First Search at the vertex selected in step 2.
6. Make the current visited node vis2[v] = true.
7. The graph is not connected if any vertex v has vis1[v] = false and vis2[v] = false.

#### C++ Programming

```#include <bits/stdc++.h>
using namespace std;
#define N 100000

bool vis1[N], vis2[N];

void dfs1(int node)
{
vis1[node] = true;

if (!vis1[i])
dfs1(i);
}

void dfs2(int node)
{
vis2[node] = true;

if (!vis2[i])
dfs2(i);
}

bool solve(int n)
{
memset(vis1, false, sizeof vis1);
dfs1(1);

// reverse direction call
memset(vis2, false, sizeof vis2);
dfs2(1);

for (int i = 0; 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;
}
return true;
}

int main()
{
int n = 3;

if (solve(n))
cout << "YES";
else
cout << "NO";

return 0;
}```

#### Output

`YES`

#### Java Programming

```import java.util.*;

class Solution
{
static int N = 1000;

static Vector<Integer>[] adj1 = new Vector[N];
static Vector<Integer>[] adj2 = new Vector[N];

static boolean[] vis1 = new boolean[N];
static boolean[] vis2 = new boolean[N];

static {
for (int i = 0; i < N; i++)
{
}
}

static void MakeGraph(int u, int v)
{
}

static void dfs1(int x)
{
vis1[x] = true;
if (!vis1[i])
dfs1(i);
}

static void dfs2(int x)
{
vis2[x] = true;
if (!vis2[i])
dfs2(i);
}

static boolean solve(int n)
{
// Call for initial direction
Arrays.fill(vis1, false);
dfs1(1);

// Call for reverse direction
Arrays.fill(vis2, false);
dfs2(1);

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;
}
return true;
}

public static void main(String[] args)
{
int n = 3;

MakeGraph(1, 2);
MakeGraph(2, 3);
MakeGraph(1, 3);

if (solve(n))
System.out.println("YES");
else
System.out.println("NO");
}
}```

#### Output

`YES`

#### Python Programming

```N = 1000

vis1 =  * N; vis2 =  * N;

def CreateGraph(u, v):
if u not in adj1 :

if v not in adj2 :

def dfs1(node) :
vis1[node] = True;
if node not in adj1 :

if (not vis1[i]) :
dfs1(i)

def dfs2(node) :
vis2[node] = True;

if node not in adj2 :

if (not vis2[i]) :
dfs2(i);

def solve(n) :

global vis1;
global vis2;
# Call for correct direction
vis1 = [False] * len(vis1);
dfs1(1);

# Call for reverse direction
vis2 = [False] * len(vis2);
dfs2(1);

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;
return True;

if __name__ == "__main__" :
n = 3;

CreateGraph(1, 2);
CreateGraph(2, 3);
CreateGraph(1, 3);

if (solve(n)) :
print("Yes");

else :
print("No");```

#### Output

`YES`