Introduction

This is my blog of programming, I take notes and leave codes of computer science problems I solved here. Be my guest to comment :)

Tuesday, November 27, 2012

uva 247 - Calling Circles


/*
Problem link
Type: Graph, DFS, Strongly connected components
Algorithm: Tarjan
*/
#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