247 - Calling Circles

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<map>
#define SZ 30
using namespace std;

int color[SZ],topsort[SZ],k,l,store[SZ];

map<string,int>mymap;
map<int,string>mymap1;
vector<int>graph[SZ];
vector<int>graph1[SZ];

void DFS(int p)
{
    color[p]=1;
    for(int i=0; i<graph[p].size(); i++)
    {
        if(color[graph[p][i]]==0)
        {
            DFS(graph[p][i]);
        }
    }
    topsort[k++]=p;
}

void DFS1(int p)
{
    color[p]=0;
    store[l++]=p;
    for(int i=0; i<graph1[p].size(); i++)
    {
        if(color[graph1[p][i]]==1)
        {
            DFS1(graph1[p][i]);
        }
    }
}

int main()
{
    int n,m,i,j,tag,a,b,test=0,u;
    string s1,s2;
    while(scanf("%d%d",&n,&m)==2)
    {
        if(n==0 && m==0)
        {
            break;
        }
        tag=0;
        for(i=1; i<=m; i++)
        {
            cin>>s1>>s2;
            if(!mymap[s1])
            {
                mymap[s1]=++tag;
                mymap1[tag]=s1;
            }
            a=mymap[s1];
            if(!mymap[s2])
            {
                mymap[s2]=++tag;
                mymap1[tag]=s2;
            }
            b=mymap[s2];
            graph[a].push_back(b);
            graph1[b].push_back(a);
        }
        k=0;

        for(i=1; i<=tag; i++)
        {
            if(color[i]==0)
            {
                DFS(i);
            }
        }
        l=0;
        if(test)
        {
            printf("\n");
        }
        printf("Calling circles for data set %d:\n",++test);
        for(i=k-1; i>=0; i--)
        {
            u=topsort[i];
            if(color[u]==1)
            {
                DFS1(u);
                cout<<mymap1[store[0]];
                for(j=1; j<l; j++)
                {
                    cout<<", "<<mymap1[store[j]];
                }
                cout<<endl;
                l=0;
            }
        }
        mymap.clear();
        mymap1.clear();
        for(i=0; i<=n; i++)
        {
            graph[i].clear();
            graph1[i].clear();
        }
    }
    return 0;
}

0 comments: (+add yours?)