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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 247 - Calling Circles

Post by brianfry713 »

Describe your algorithm.

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

Re: 247 - Calling Circles

Post by @ce »

-@ce
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 247 - Calling Circles

Post by brianfry713 »

Input:

Code: Select all

15 13
drx fmpqczsus
fmpqczsus ismtdgbs
znwx liq
drx copxbrhmrlka
k glvapurny
znwx liq
umjjuf fufarfxgygbjaty
cbeajzhnz fmpqczsus
uwwteubi umjjuf
umjjuf vna
fmpqczsus k
wjudt xqy
ismtdgbs k
0 0
AC output:

Code: Select all

Calling circles for data set 1:
drx
fmpqczsus
ismtdgbs
znwx
liq
copxbrhmrlka
k
glvapurny
umjjuf
fufarfxgygbjaty
cbeajzhnz
uwwteubi
vna
wjudt
xqy
Check input and AC output for thousands of problems on uDebug!
ZALAT
New poster
Posts: 1
Joined: Mon Aug 12, 2013 11:49 am

Re: 247 - Calling Circles

Post by ZALAT »

Code: Select all

AC :) was a stupid mistake
i dont know why using kosaraju algorithm doesnt work for it keep getting WA although it seems fine as it finds the strongly connected components , any help would be appreciated or any test cases
Saminur Islam
New poster
Posts: 4
Joined: Tue Dec 10, 2013 10:49 am

Re: 247 - Calling Circles

Post by Saminur Islam »

i cant understand why i am getting WA ..... i cant find the bug of the code any help would be appreciated

Code: Select all

#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<set>
#include<list>
#include<utility>
#include<fstream>
#include<cmath>
#include <limits>

using namespace std;

#define MAX 27
enum colors {BLACK, WHITE, GRAY};
int color[MAX],vertex, edge;

vector<int> sccVertex;
list<int> orderedList;

void DFS_VISIT(vector<int> G[], int u)
{
    color[u] = GRAY;
    for(int v=0; v<G[u].size(); v++)
    {
        if(color[G[u][v]] == WHITE) DFS_VISIT(G,G[u][v]);
    }
    color[u] = BLACK;
    orderedList.push_front(u);
}

void DFS(vector<int> G[])
{
    for(int u=0; u<=vertex; u++)
    {
        color[u] = WHITE;
    }
    for(int u=1; u<=vertex; u++)
    {
        if(color[u] == WHITE) DFS_VISIT(G,u);
    }
}


void DFS_VISIT_GT(vector<int> G[], int u)
{
    color[u] = GRAY;
    for(int v=0; v<G[u].size(); v++)
    {
        if(color[G[u][v]] == WHITE)
        {
            DFS_VISIT_GT(G,G[u][v]);
        }
    }
    color[u] = BLACK;
    sccVertex.push_back(u);
}

void DFS_GT(vector<int> G[],string arr[])
{
    list<int>::iterator it;
    for(int u=0; u<=vertex; u++) color[u] = WHITE;
    for(it=orderedList.begin(); it != orderedList.end(); ++it)
    {

        if(color[*it] == WHITE)
        {
            DFS_VISIT_GT(G,*it);
            sort(sccVertex.rbegin(), sccVertex.rend());
            int size;
            size=sccVertex.size();
            int k=1;
            while(!sccVertex.empty())
            {
                int id;
                id=sccVertex.back();
                sccVertex.pop_back();
                if(k!=size)
                {
                    cout<<arr[id]<<", ";
                    k++;
                }
                else if(k==size) cout<<arr[id]<<endl;
            }
        }
    }
}

void STRONGLY_CONNECTED_COMPONENTS(vector<int> G[], vector<int> GT[],string arr[])
{
    DFS(G);
    DFS_GT(GT,arr);
}

int main(void)
{
    //freopen("scc.txt", "r", stdin);
    int DT=0;
    while(cin >> vertex >> edge)
    {
        if(vertex==0||edge==0) break;
        sccVertex.clear();
        orderedList.clear();
        DT++;
        vector<int> G[MAX];
        vector<int> GT[MAX];
        map<string,int> M;
        string arr[MAX];
        char u[25],v[25];
        int i=0;
        for(int e=1; e<=edge; e++)
        {
            cin >> u >> v;
            if(M.find(u)==M.end())
            {
                M.insert(make_pair(u,i));
                arr[i]=u;
                i++;
            }
            if(M.find(v)==M.end())
            {
                M.insert(make_pair(v,i));
                arr[i]=v;
                i++;
            }
            G[M[u]].push_back(M[v]);
            GT[M[v]].push_back(M[u]);
        }
        if(DT>1)cout<<endl;
        printf("Calling circles for data set %d:",DT);
        STRONGLY_CONNECTED_COMPONENTS(G,GT,arr);
    }
    return 0;
}
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 247 - Calling Circles

Post by brianfry713 »

brianfry713 wrote: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!
kev_yu
New poster
Posts: 3
Joined: Sun Dec 29, 2013 8:46 am

Re: 247 - Calling Circles

Post by kev_yu »

el cheeto wrote: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.
I replace every vector.assign(n,0) and vector.clear() with for (int i=0;i<=n;i++) { vector=0 } and get accepted. I think vector.clear() only clear the space from vector.push_back(). It made me WA for 5 consecutive times.

Sorry for my bad english
Post Reply

Return to “Volume 2 (200-299)”