DFS Strongly Connected Component (SCC) | Strongly Connected Component in C

 
#include<stdio.h>
#define sz 100
int n, e, mat[sz][sz], mat_rev[sz][sz], visited[sz], k, start[sz], finish[sz], stk[sz], TOP = -1;
bool isEmpty()
{
    if(TOP == -1)
        return true;
    return false;
}
void PUSH(int i)
{
    stk[++TOP] = i;
}
int POP()
{
    return stk[TOP--];
}
void DFS(int i)
{
    for(int j=0;j<n;j++)
    {
        if(mat[i][j] == 1 && visited[j] == 0)
        {
            start[j] = ++k;
            visited[j] = 1;
            DFS(j);
            finish[j] = ++k;
            PUSH(j);
        }
    }
}
void DFS2(int i)
{
    printf("%c ", i+'A');
    for(int j=0;j<n;j++)
    {
        if(mat_rev[i][j] == 1 && visited[j] == 1)
        {
            visited[j] = 2;
            DFS2(j);
        }
    }
}
void SCC()
{
    int item;
    printf("\n\nStrongly Connected Components:\n");
    while(!isEmpty())
    {
        item = POP();
        if(visited[item] == 1)
        {
            visited[item] = 2;
            printf("\n");
            DFS2(item);
        }
    }
}
int main()
{
    int i, j;
    char a, b;
    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(" %c %c", &a, &b);
        mat[a-'A'][b-'A'] = 1;
        mat_rev[b-'A'][a-'A'] = 1;
    }
    k = 0;
    for(i=0;i<n;i++)
    {
        if(visited[i] == 0)
        {
            start[i] = ++k;
            visited[i] = 1;
            DFS(i);
            finish[i] = ++k;
            PUSH(i);
        }
    }
    printf("\n\n");
    for(i=0;i<n;i++)
    {
        printf("node %c: %d/%d\n", i+'A', start[i], finish[i]);
    }
    SCC();
    return 0;
}
/*
8 14
A B
B C
B F
B D
C F
C A
D E
D G
E D
E H
F G
G F
H H
H G
*/

Post a Comment

Previous Post Next Post