Topological Sort DFS | Topological Sort in C

 
#include <stdio.h>
#include <stdbool.h>
#define SZ 100
#define STK_SZ 1000

int n, e, visited[SZ], mat[SZ][SZ],s[SZ], f[SZ], k, STK[STK_SZ],TOP = -1;
bool isEmpty()
{
    if(TOP == -1)
        return true;
    return false;
}
void Push(int item)
{
    STK[++TOP] = item;
}
int Pop()
{
    return STK[TOP--];
}
void DFS(int i)   //here i as a current
{
    int j;
    for(j=0;j<n;j++)
    {
        if(visited[j] == 0 && mat[i][j] == 1)
        {
            s[j] = ++k;
            visited[j] = 1;
            DFS(j);
            f[j] = ++k;
            Push(j);
        }
    }
    return;
}
int main()
{
    int a, b, i, j;
    scanf("%d %d", &n, &e);
    for(i=0;i<n;i++)
    {
        visited[i] = 0;
        for(j=0;j<n;j++)
            mat[i][j] = 0;
    }
    for(i=0;i<e;i++)
    {
        scanf("%d %d", &a, &b);
        mat[a][b] = 1;
    }
    k = 0;
    for(i=0;i<n;i++)
    {
        if(visited[i]==0)
        {
            s[i] = ++k;
            visited[i] = 1;
            DFS(i);
            f[i] = ++k;
            Push(i);
        }
    }
    printf("\n\nStarting and Finishing time:\n");
    for(i=0;i<n;i++)
    {
        printf("node %d: %d/%d\n", i, s[i], f[i]);
    }
    printf("\n\nTopologically sorted nodes:\n");
    while(!isEmpty())
    {
        printf("%d ", Pop());
    }
}

/*
Input:
8 9
0 1
0 2
1 2
3 4
3 7
4 5
4 7
5 6
7 6
*/

Post a Comment

Previous Post Next Post