Finding Strongly Connected Components (SCC)

#include <iostream>

#include <cstdio>

#include <vector>

#include <map>

#include <string>

#include <cstring>

using namespace std;

#define siz 1000009

vector <int> vec[siz];

vector <int> vecc[siz];

vector <int> group;

vector <int> sortlist;

map <string, int> mp;

map <int, string> pa;

int color[siz];

int n,m;

string as,bs;



void dfs(int n){

    color[n]=1;



    for(int i=0;i<vec[n].size();i++){

        int v=vec[n][i];

        if(color[v]==0){

            dfs(v);

        }

    }

    sortlist.push_back(n);

    color[n]=2;

}

void dfs2(int n){

    color[n]=1;

    group.push_back(n);

    for(int i=0;i<vecc[n].size();i++){

        int v=vecc[n][i];

        if(color[v]==0){

            dfs2(v);

        }

    }



    color[n]=2;

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("input.txt","r",stdin);

    #endif

    int k=1;

    while(scanf("%d%d",&n,&m)==2){

        if(n==0&&m==0) break;

        if(k!=1) printf("\n");

        for(int i=0;i<=n;i++)

            color[i]=0;

        int index=1;

        for(int i=0;i<m;i++){

            cin>>as>>bs;

            if(mp[as]==0){

                mp[as]=index;

                pa[index]=as;

                index++;

            }

            if(mp[bs]==0){

                mp[bs]=index;

                pa[index]=bs;

                index++;

            }

            vec[mp[as]].push_back(mp[bs]);

            vecc[mp[bs]].push_back(mp[as]);

        }



        for(int i=1;i<=n;i++)

            if(color[i]==0) dfs(i);



        for(int i=0;i<=n;i++)

            color[i]=0;



        int cnt=0;

        printf("Calling circles for data set %d:",k++);

        for(int i=sortlist.size()-1;i>=0;i--){

            if(color[sortlist[i]]==0){

                //group.push_back(sortlist[i]);

                for(int j=0;j<group.size();j++){

                    if(j!=0) printf(", ");

                    printf("%s",pa[group[j]].c_str());

                    //cout<<pa[group[j]];

                }

                printf("\n");

                group.clear();

                dfs2(sortlist[i]);

                cnt++;

            }

        }

        for(int j=0;j<group.size();j++){

            if(j!=0) printf(", ");

            printf("%s",pa[group[j]].c_str());

        }

        printf("\n");

        group.clear();

        sortlist.clear();

        for(int i=0;i<=n;i++){

            vec[i].clear();

            vecc[i].clear();

        }

        mp.clear();

        pa.clear();

    }

    return 0;

}