New update is available. Click here to update.

Last Updated: 31 Mar, 2021

Difficulty: Moderate

```
Nodes are numbered from 0 to N - 1.
The graph given is connected.
Print the vertices in sorted order.
```

```
The following is an example of DAG i.e a directed graph with no cycles in it.
```

```
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.
The first line of each test case contains two integers separated by a single space ‘N’ and ‘M’, where ‘N’ denoting the number of the vertices and ‘M’ denoting the number of edges in the graph.
The next ‘M’ lines of each test case contain two integers ‘X’ and ‘Y’ separated by a single space, here ‘X’ and ’Y’ the vertices connected by a directed edge from ‘X’ to ‘Y’.
```

```
For each test case, print the smallest set of vertices from which all the nodes in the graph are reachable in sorted order.
Print the output of each test case on a new line.
```

```
You don’t need to print anything; It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 5
2 <= N <= 10^5
1 <= M <= 10^5
0 <= X,Y <= N - 1
Time Limit: 1 sec
```

```
2
6 5
0 1
0 2
2 5
3 4
4 2
5 4
0 1
2 1
1 4
2 4
```

```
0 3
0 2 3
```

```
For the first test case,
We can’t cover all the nodes by only one vertex.
From, 0 we can cover 0, 1, 2, 5.
From, 2 we can cover 2, 5.
From, 3 we can cover 2, 3, 4, 5.
From, 5 we can cover 5.
From, 0, 3 we can cover 0, 1, 2, 3, 4, 5.
For the second test case,
From, 0, 2, 3 we can cover the whole graph.
```

```
2
4 5
0 1
0 2
0 3
1 2
2 3
2 1
1 0
```

```
0
1
```

The idea here is that all the vertices with **indegree** zero should be included in the final ans because these vertices are not reachable from any other nodes. All the other nodes with **indegree** > 0 can be reached from some other nodes.

**The algorithm is as follows:**

- Declare an array
**indegree**of size**N**to store the indegree of each vertex, and for every i set**indegree[i]**to 0. - Declare an array
**ans**to store all the nodes using which cover the whole graph. - Traverse all the
**edges**in the graph,- Let the current edge be directed from
**x**to**y.** - Increment
**indegree[y]**by 1.

- Let the current edge be directed from
- Iterate from
**vertex = 0 to N - 1,**- If
**indegree[vertex]**is**0**,- Append
**vertex**to**ans**.

- Append

- If
- Return the
**ans**.

SIMILAR PROBLEMS

Minimum Swaps To Make Identical Array

Posted: 22 Jan, 2022

Difficulty: Moderate

Find Center of Star Graph

Posted: 26 Jan, 2022

Difficulty: Easy

Critical Connections in a Network

Posted: 27 Jan, 2022

Difficulty: Hard

Critical Connections in a Network

Posted: 27 Jan, 2022

Difficulty: Hard

Critical Connections in a Network

Posted: 27 Jan, 2022

Difficulty: Hard

COUNT ISLANDS

Posted: 14 Sep, 2022

Difficulty: Moderate

Distance to a Cycle in Undirected Graph

Posted: 7 Nov, 2022

Difficulty: Moderate

Popular Interview Problems: