CODEWITHSUNDEEP
c++algorithmgraph
sudeepdino008
sudeepdino008

Reputation: 3364

strongly connected components for spoj's BOTTOM

I am trying to solve http://www.spoj.com/problems/BOTTOM/

Here are the steps I am following:

1) Find the strongly connected components using Kosaraju's algorithm. 2) Consider a strongly connected component. Consider an edge u. Now consider all edges from u to some vertice v. If v lies in some other SCC, eliminate the whole strongly conected component. Else include all the elements in the solution.

However, I am constantly getting WA. Please help.

Here is my code:

struct Graph{
    int V;
    vector<int> *adj;
    vector<int> *auxiliary;
    vector<vector<int> > components;


    Graph(int _V)
    {
        V=_V;
        adj=new vector<int>[V+1];
        auxiliary=new vector<int>[V+1];
    }
    void addEdge(int u, int v)
    {
        adj[u].push_back(v);
        auxiliary[v].push_back(u);
    }
    void DFS(int u, bool *visited,stack<int> &nodes)
    {
        visited[u]=true;
        int t;
        stack<int> state;
        bool present;
        state.push(u);
        while(!state.empty())
        {
            t=state.top();
            visited[t]=true;
            present=false;
            for(vector<int>::iterator it=adj[t].begin();it!=adj[t].end();it++)
            {
                if(!visited[*it])
                {
                    visited[*it]=true;
                    state.push(*it);
                    present=true;
                }
            }
            if(!present)
            {
                nodes.push(state.top());
                state.pop();
            }

        }
    }
    void DFSutil(int u,bool *visited,set<int> &members)
    {
        visited[u]=true;
        stack<int> state;
        int t;
        bool present;
        state.push(u);
        while(!state.empty())
        {
            t=state.top();
            present=false;
            for(vector<int>::iterator it=auxiliary[t].begin();it!=auxiliary[t].end();it++)
            {
                if(!visited[*it])
                {
                    visited[*it]=true;
                    present=true;
                    state.push(*it);
                }
            }
            if(!present)
            {
                members.insert(state.top());
                state.pop();
            }
        }
    }
    void kosaraju()
    {
        bool visited[V+1];
        memset(visited,false,sizeof(visited));
        stack<int> nodes;
        int i,t;
        //store the nodes, 1st DFS
        for(i=1;i<=V;i++)
        {
            if(!visited[i])
                DFS(i,visited,nodes);
        }
        //run DFS on the auxiliary(transposed) graph
        set<int> members;
        vector<int> answers;
        memset(visited,false,sizeof(visited));
        while(!nodes.empty())
        {
            t=nodes.top();
            members.clear();
            if(!visited[t])
            {
                DFSutil(t,visited,members);
                set<int>::iterator it;
                for(it=members.begin();it!=members.end();it++)
                {
                    vector<int>::iterator itt;
                    for(itt=adj[*it].begin();itt!=adj[*it].end();itt++)
                    {
                        if(!present(members,*itt))
                            break;
                    }
                    if(itt!=adj[*it].end())
                        break;
                }
                if(it==members.end())
                {
                    for(it=members.begin();it!=members.end();it++)
                        answers.pb(*it);
                }
            }
            nodes.pop();
        }
        sort(answers.begin(),answers.end());
        tr(answers,itt)
            printf("%d ",*itt);
        printf("\n");
    }

};

Upvotes: 1

Views: 924

Answers (1)

mrip
mrip

Reputation: 15163

At first glance, it looks like your depth-first search (assuming DFS is supposed to be depth-first) might not actually be depth-first, but rather a breadth-first-search, since it adds all of the unvisited neighbors to the search queue immediately. I think you might need to add a break statement:

for(vector<int>::iterator it=adj[t].begin();it!=adj[t].end();it++)
        {
            if(!visited[*it])
            {
                visited[*it]=true;
                state.push(*it);
                present=true;
   -----------> break;
            }
        }

In comments, sudeepdino008 correctly pointed out that DFS can be implemented with a stack, but in this case I believe that vertices shouldn't be marked as visited until they are removed from the stack:

for(vector<int>::iterator it=adj[t].begin();it!=adj[t].end();it++)
        {
            if(!visited[*it])
            {
   ---------->   //visited[*it]=true;
                state.push(*it);
                present=true;
            }
        }

Here's the problem: Consider a simple graph 

1->2
1->3
3->2

With the original algorithm, vertices will be added to nodes in the order (3,2,1) rather than (2,3,1). This means that, in the second part of the algorithm, when the backwards BFS is performed, 2 will be selected before 3, and the algorithm will incorrectly output that (2,3) is a strongly connected component.

Upvotes: 2

Related Questions