247 - Calling Circles

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

[@ce]

I have used this algorithm.
http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm

[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

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

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]

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.

[kev_yu]

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