247 - Calling Circles

[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]

I used Warshall's and got AC, but it wasn't just Warshall.. what else do you do?

[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]

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]

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]

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..?

[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]

Thanks for help asif_rahman0..!
I got it.. ^^

[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]

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]

Removed

[brianfry713]

Doesn't match the sample I/O.

[Ronok1307]

Getting WA

Code: Select all

Removed after AC

[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.

[@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;
                  }
            }
      }
}