#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 50;
class Customer {
public:
string name;
int id;
Customer () {
name = "";
id = 0;
}
};
class Stack {
public:
int val[maxn];
int top;
Stack () { top = 0;}
void push(int v) { val[++top] = v;}
int pop() { return(val[top--]);}
};
Customer list[maxn];
bool a[maxn][maxn], visited[maxn];
int n,m,low[maxn],num[maxn],dfsCnt;
Stack st;
bool readfile();
int find(string name);
string find(int id);
void tarjan(int u);
int main() {
int test = 0;
while (readfile())
{
test++;
if (test>1) cout << endl;
printf("Calling circles for data set %d:\n",test);
for (int i=1; i<=n; i++)
if (num[i]==0) tarjan(i);
}
return 0;
}
int find(string name) {
for (int i=1; i<=n; i++)
if (list[i].name==name) return(list[i].id);
return(0);
}
string find(int id) {
for (int i=1; i<=n; i++)
if (list[i].id==id) return(list[i].name);
}
bool readfile() {
cin >> n >> m;
if (n==0 && m==0) return(false);
string u, v;
int cnt = 0, dfsCnt = 0;
memset(visited,false,sizeof(visited));
memset(a,false,sizeof(a));
memset(low,0,sizeof(low));
memset(num,0,sizeof(num));
for (int i=1; i<=n; i++)
{
list[i].name = "";
list[i].id = 0;
}
st.top = 0;
for (int i=1; i<=m; i++)
{
cin >> u >> v;
int x = find(u);
int y = find(v);
if (x==0)
{
cnt++;
list[cnt].name = u;
list[cnt].id = cnt;
x = cnt;
}
if (y==0)
{
cnt++;
list[cnt].name = v;
list[cnt].id = cnt;
y = cnt;
}
a[x][y] = true;
}
return(true);
}
void tarjan(int u) {
low[u] = num[u] = dfsCnt++;
visited[u] = 1;
st.push(u);
for (int v=1; v<=n; v++)
if (a[u][v])
{
if (num[v]==0) tarjan(v);
if (visited[v]) low[u] = min(low[u],low[v]);
}
if (low[u]==num[u])
{
while (1)
{
int v = st.pop();
visited[v] = 0;
if (u!=v) cout << find(v) << ", ";
else
{
cout << find(v) << endl;
break;
}
}
}
}
No comments:
Post a Comment