## 247 - Calling Circles

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

### 247 - Calling Circles

If I understood the problem statement correctly, a calling circle is a strongly connected component of the call graph. I tried to determine these, but got WA with Tarjan's as well as with Warshall's algorithm. Is there anything I missed?
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I used Warshall's and got AC, but it wasn't just Warshall.. what else do you do?
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
I'll describe some theoretical thoughts:

Let R be the relation given by the phone calls. I use Warshall's algorithm to find its transitive closure R'. Let S be the relation with xSy iff (xR'y and yR'x). S is an equivalence relation (reflexive, symmetric and transitive) and the equivalence classes are the calling circles.

For each name x I then print all names y with xSy and mark every y as "done", so I don't print the same calling circle twice.
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
If I understood the problem statement correctly, a calling circle is a strongly connected component of the call graph.
You are right.
I got accepted with Tarjan's algorithm, so this shouldn't be the reason for your WA. Since this problem has a special judge, try to be extremely careful with formatting, maybe you will get WA for cases that are normally judged as PE.
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
I just found my (really stupid) mistake: I put the case number variable in the wrong line, making it a char. Both my Warshall and Tarjan implementations got AC when changing it to int.

Thanks for your replies!
helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Please tell me what's wrong with my code ..
I try to implement Tarjan's algorithm..
I think it's all right.. but getting WA..

Code: Select all

``````code removed..
``````

And anybody would tell me how this problem could be solved with Warshell..?
Last edited by helloneo on Sun Apr 30, 2006 5:17 pm, edited 1 time in total.
asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
i think u can check ur problem's sample I/O:D then u will get ur fault.

u can also do it by Floyd Warshall. just go throught the normal algo then just follow the relation with xSy iff (xR'y and yR'x) with recursive checking.

hope it will help
helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Thanks for help asif_rahman0..!
I got it.. ^^
el cheeto
New poster
Posts: 9
Joined: Mon Feb 13, 2006 12:40 am
Location: Mexico

### Re: 247 - Calling Circles

Hi!! I,ve been using Tarjan's algorithm to solve this problem, but I keep getting WA. I don't know if there are some special (tricky) cases. I've used this algo for other problems and it had worked correctly until now. Any help would be great. Thank you.

my code:

Code: Select all

``````#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <map>

#define N 101

using namespace std;

int G[N][N];
int S[N], LOW[N], R[N], L[N];
int n, m, nVertex, nComponents;
map<string,int> person;
vector<string> name(N);

void Tarjan();
void DFS(int v);
int min(int a, int b);

int main()
{
int i, j, k;
int a, b, count = 0;
string str1, str2;

//freopen("out.txt", "w", stdout);

while(cin >> n >> m)
{
if(n == 0 && m == 0)
break;

if(count++ > 0)
cout << endl;

person.clear();
memset(G,0,sizeof(G));
memset(R,0,sizeof(R));
memset(S,-1,sizeof(S));

for(i=0; i<m; i++)
{
cin >> str1 >> str2;

if(person.find(str1) == person.end())
{
name[person.size()] = str1;
person[str1] = person.size();
}

if(person.find(str2) == person.end())
{
name[person.size()] = str2;
person[str2] = person.size();
}

a = person[str1];
b = person[str2];

G[a][b] = 1;
}

cout << "Calling circles for data set " << count << ":" << endl;

Tarjan();
}

return 0;
}

void Tarjan()
{
int i;

for(i=0; i<n; i++)
{
if(S[i] == -1)
{
nVertex = 0;
nComponents = 0;
DFS(i);
}
}
}

void DFS(int v)
{
int k, c;

S[v] = nVertex++;
L[nComponents++] = v;	//Add to the stack
LOW[v] = S[v];
R[v] = 1;				//v is in the stack

for(int i=0; i<n; i++)
{
if(G[v][i] == 1)	//If there is a conexion v -> i
{
if(S[i] == -1)	//if it's a tree node (unvisited)
{
DFS(i);
LOW[v] = min(LOW[v],LOW[i]);
}
else if(R[i] == 1)	//if i is on the stack
LOW[v] = min(LOW[v],S[i]);
}
}

if(S[v] == LOW[v])
{
c = 0;
do
{
k = L[nComponents-1];	//Quit k from the stack
R[k] = 0;				//k is no more on the stack
nComponents--;

if(c++ == 0)
cout << name[k];
else
cout << ", " << name[k];
}
while(k != v && nComponents > 0);

cout << endl;
}
}

int min(int a, int b)
{
if(a < b)
return a;
else
return b;
}``````
el cheeto
New poster
Posts: 9
Joined: Mon Feb 13, 2006 12:40 am
Location: Mexico

### Re: 247 - Calling Circles

Got Accepted now. I changed all the C++ I/O for C I/O, change all the cin for scanf, and cout for printf, and quit all the classes of the standard library, such as map, vector, etc.. and use simple arrays. Hope it helps. I really don't know why this happens, but it worked.
ljacs
New poster
Posts: 5
Joined: Wed Sep 05, 2012 5:53 am

### Tarjan's algorithm for finding SCCs (Prob. 247)

Removed
Last edited by ljacs on Tue Oct 16, 2012 7:48 am, edited 1 time in total.
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: Tarjan's algorithm for finding SCCs (Prob. 247)

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!
Ronok1307
New poster
Posts: 8
Joined: Tue May 29, 2012 7:37 pm

### Re: 247 - Calling Circles

Getting WA

Code: Select all

``Removed after AC``
Last edited by Ronok1307 on Sat Jan 26, 2013 4:05 am, edited 1 time in total.
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 247 - Calling Circles

I got AC in 0.024 sec by a brute force of all people that each person calls either directly or through an intermediate person. Then print each set of people that call each other.
Check input and AC output for thousands of problems on uDebug!
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### 247 - Calling Circles

Getting WA....plzz help with some test cases or the bug in the code...

Code: Select all

``````#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<deque>
#include<queue>
#include<map>
using namespace std;

typedef long long int L;
typedef unsigned long long int U;

vector<int>v[30];
vector<int>r[30];
map<string,int>m;
map<string,int>::iterator it;
map<int,int>f;
int visit[30];
int fval[30];
vector<string>nm;
stack<int>stk;

main()
{
int n,c;
for(int t = 1;;t++)
{
m.clear();
f.clear();
nm.clear();
cin>>n>>c;
if(!(n|c))
break;
int k = 0;
for(int i = 0;i<n;i++)
{
visit[i] = 0;
v[i].clear();
r[i].clear();
}
for(int i = 0;i<c;i++)
{
int a = -1, b = -1;
string str1,str2;
cin>>str1>>str2;
it = m.find(str1);
if(it == m.end())
{
nm.push_back(str1);
m.insert(make_pair(str1,k));
a = k++;
}
else
a = it->second;
it = m.find(str2);
if(it == m.end())
{
nm.push_back(str2);
m.insert(make_pair(str2,k));
b = k++;
}
else
b = it->second;
v[a].push_back(b);
r[b].push_back(a);
}
k = 0;
for(int i =  n-1;i>=0;i--)
{
if(!visit[i])
{
int x;
visit[i] = 1;
stk.push(i);
while(!stk.empty())
{
x = stk.top();
bool child = 0;
for(int j = 0;j<r[x].size();j++)
{
if(!visit[r[x][j]])
{
child = 1;
visit[r[x][j]] = 1;
stk.push(r[x][j]);
}
}
if(!child)
{
x = stk.top();
stk.pop();
fval[x] = k;
f.insert(make_pair(k++,x));
}
}
}
}
for(int i = 0;i<n;i++)
visit[i] = 0;
if(t != 1)
cout<<endl;
printf("Calling circles for data set %d:\n", t);
for(int i = n-1;i>=0;i--)
{
bool first = 1;
int x = f.find(i)->second;
if(!visit[x])
{
visit[x] = 1;
stk.push(x);
while(!stk.empty())
{
x = stk.top();
stk.pop();
if(first)
{
cout<<nm[x];
first = 0;
}
else
cout<<", "<<nm[x];
for(int j = 0;j<v[x].size();j++)
{
if(!visit[v[x][j]])
{
visit[v[x][j]] = 1;
stk.push(v[x][j]);
}
}
}
if(!first)
cout<<endl;
}
}
}
}
``````
-@ce