/* 7(b). W.A.P. to print all nodes that are reachable from a given starting node in a digraph using Depth First Search (DFS). */

#include<stdio.h>
#include<conio.h>
int n,visited[10],a[10][10],flag = 1;
void Dfs(int node)
{
    int i;
    visited[node] = 1;
    printf("Vertex : %d\n",node+1);
    for (i = 0; i < n; i++)
        if (a[node][i] == 1 && visited[i] == 0)
        {
            Dfs(i);
            flag = 0;
        }
}
void main()
{
    int i,j,ver;
    clrscr();
    printf("\nEnter the no. of nodes : ");
    scanf("%d",&n);
    printf("\nEnter the adjacent matrix :\n");
    for (i = 0; i < n; i++)
    {    
        for (j = 0; j < n; j++)
            scanf("%d",&a[i][j]);
            visited[i] = 0; /* All the nodes are unvisited. */
    }
    printf("\nEnter starting node : ");    
    scanf("%d",&ver);
    printf("\Nodes reachable from ");
    Dfs(ver-1);
    if (flag)
        printf("None.");
        getch();
}
/* OUTPUT
Enter the no. of nodes : 5
Enter the adjacent matrix :
0 1 1 0 0
1 0 0 1 0
1 0 0 1 0
0 1 1 0 0
0 0 0 0 0
Enter starting node : 1

Nodes reachable from Vertex : 1
Vertex : 2
Vertex : 3
Vertex : 4


Enter the no. of nodes : 3
Enter the adjacent matrix :
0 1 1
1 0 0
0 0 0
Enter starting node : 3

Nodes reachable from Vertex : 3
None.
*/