#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;
}
#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?)
Post a Comment