247 - Calling Circles.cpp

#include<bits/stdc++.h>
using namespace std;

int n,e;
vector<int>v1[1005],v2[1005],comp[1005];
bool visited[1005];
int mark;
stack<int>s;
map<string,int>m;
map<int,string>mp;


void toposort(int x){

    visited[x]=true;
    //cout<<x<<"\n";

    for(int i=0;i<v1[x].size();i++){

        int xx = v1[x][i];

        if(visited[xx]==false) toposort(xx);

    }

    s.push(x);

    //cout<<"push "<<x<<"\n";

}

void dfs(int x){

    comp[mark].push_back(x);

    //cout<<x<<" ";

    visited[x]=true;

    for(int i=0;i<v2[x].size();i++){

        int xx = v2[x][i];

        if(visited[xx]==false) dfs(xx);

    }

}

void FindScc(){

    stack<int>emp;

    swap(s,emp);

    memset(visited,false,sizeof(visited));

    mark=0;

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

        comp[i].clear();
    }

    //cout<<"here\n";

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

        if(visited[i]==false) toposort(i);

    }

    memset(visited,false,sizeof(visited));

    while(!s.empty()){

        int u = s.top();

        //cout<<u<<"\n";

        s.pop();

        if(visited[u]==false){

            mark++;
            dfs(u);

        }

    }

}

int main(){

    int pp=1;
    while(cin>>n>>e){

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



        string aa,bb;
        m.clear();
        mp.clear();
        int a=1;
        while(e--){

            cin>>aa>>bb;

            if(m.find(aa)==m.end()){
                m[aa]=a;
                mp[a]=aa;
                a++;
            }

            if(m.find(bb)==m.end()){
                m[bb]=a;
                mp[a]=bb;
                a++;
            }


            v1[m[aa]].push_back(m[bb]);
            v2[m[bb]].push_back(m[aa]);

        }

        FindScc();

        if(pp!=1) cout<<"\n";

        cout<<"Calling circles for data set "<<pp<<":\n";

        for(int i=1;i<=mark;i++){

            for(int j=0;j<comp[i].size();j++){

                cout<<mp[comp[i][j]];
                if(j!=comp[i].size()-1) cout<<", ";

            }

            cout<<"\n";

        }

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

            v1[i].clear();
            v2[i].clear();
        }

        pp++;

    }

}