DFS,Top Sort & SCC

DFS_example.cpp

#include<iostream>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#define PI 2*acos(0.0)
#define SIZE 1000000
#define endl '\n'
int caseno=1;
#define CP() printf("Case %d: ",caseno++)
#define R() freopen("in.txt","r",stdin)
#define W() freopen("out.txt","w",stdout)
#define sfi(_i) scanf("%d",&_i)
#define sfc(_c) scanf("%c",&_c)
#define pf1(_i) cout<<_i
#define pfl() cout<<endl
#define pfs() printf(" ")
#define mem(_ar,_v) memset(_ar,_v,sizeof(_ar))
#define FOR(i,a,b) for(i=(a);i<(b);i++)
#define REV(i,a,b) for(i=(a);i>=(b);i--)
using namespace std;

#define SZ 30
void UndirInput();
void DirInput();
void DisplayMatrix();
void DFS();
void DFSvis(int);
void DFS2();
void DFSvis2(int);
int G[SZ][SZ],GR[SZ][SZ];
int color[SZ],color2[SZ],dis[SZ], fin[SZ];
int n,e,scount=0;
int time=0;
stack<int>T,SCC;
queue<int>D;

int main() {
    int i;
    DirInput();
    DFS();
    DFS2();
    pfl(); pfl();
    DisplayMatrix();
    pfl(); pfl();
    pf1("Node\tDiscovery\tFinish\n");
    FOR(i,0,n) {
        pf1(i); pf1("\t");
        pf1(dis[i]); pf1("\t\t");
        pf1(fin[i]); pfl();
    }
    pfl(); pfl();
    pf1("Topological Order:\n");
    while(!T.empty()) {
        pf1(T.top()); pfl();
        T.pop();
    }
    pfl(); pfl();
    pf1("Sequence of Discovery\n");
    while(!D.empty()) {
        pf1(D.front()); pfl();
        D.pop();
    }
    pfl(); pfl();
    pf1("Strongly Connected Components: "); pf1(scount);
    pfl();
    return 0;
}

void UndirInput() {
    int i,u,v;
    sfi(n); sfi(e);
    mem(G,0);
    FOR(i,0,e) {
        sfi(u); sfi(v);
        G[u][v]=1; G[v][u]=1;
    }
}

void DirInput() {
/*
12 16
1 0
1 2
2 4
4 5
5 6
3 1
3 7
7 4
7 8
7 9
7 6
8 9
9 6
10 0
10 11
11 0
*/

/*
10 18
0 2
0 1
0 9
1 2
1 3
1 4
2 6
3 5
4 8
5 2
5 4
5 7
5 8
5 6
6 7
7 8
9 1
9 4
*/


    int i,u,v;
    sfi(n); sfi(e);
    mem(G,0);
    FOR(i,0,e) {
        sfi(u); sfi(v);
        G[u][v]=1;
        GR[v][u]=1;
    }
}

void DisplayMatrix() {
    int i,j;
    FOR(i,0,n) {
        FOR(j,0,n) {
            pf1(G[i][j]);
            pfs();
        }
        pfl();
    }
}

void DFS() {
    //while(!T.empty()) T.pop();
    //while(!D.empty()) D.pop();
    mem(color,0);
    time=0;
    int i,j;
    FOR(i,0,n) {
        if(color[i]==0) {
            DFSvis(i);
        }
    }
}

void DFSvis(int u) {
    color[u]=1;
    dis[u]=++time;
    D.push(u);
    int i;
    FOR(i,0,n) {
        if(G[u][i]) {
            if(color[i]==0)
                DFSvis(i);
        }
     }
     fin[u]=++time;
     T.push(u);
     SCC.push(u);
     color[u]=2;
}


void DFS2() {
    //while(!T.empty()) T.pop();
    //while(!D.empty()) D.pop();
    mem(color2,0);
    scount=0;
    int i,j;
    while(!SCC.empty()) {
        i=SCC.top();
        SCC.pop();
        if(color2[i]==0) {
            DFSvis2(i);
            scount++;
        }
    }
}

void DFSvis2(int u) {
    color2[u]=1;
    int i;
    FOR(i,0,n) {
        if(GR[u][i]) {
            if(color2[i]==0)
                DFSvis2(i);
        }
     }
     color2[u]=2;
}