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

Post by Christian Schuster »

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:

Post by Larry »

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

Post by Christian Schuster »

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.
Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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

Post by Christian Schuster »

I just found my (really stupid) mistake: I put the case number variable in the wrong line, making it a char. :oops: 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

Post by helloneo »

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

Post by asif_rahman0 »

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

Post by helloneo »

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

Post by el cheeto »

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

Post by el cheeto »

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)

Post by ljacs »

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)

Post by brianfry713 »

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

Post by Ronok1307 »

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

Post by brianfry713 »

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

Post by @ce »

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
Post Reply

Return to “Volume 2 (200-299)”