spoj底部强连通分量

Question

我正在努力解决http://www.spoj.com/problems/BOTTOM/

以下是我要采取的步骤：

1)利用Kosaraju算法求出强连通分量。2)考虑一个强连通分量。考虑边u，现在考虑从u到某些点的所有边v，如果v位于其他SCC中，则消除整个强相合分量。否则，包括解决方案中的所有元素。

然而，我不断地得到WA。请帮帮忙。

这是我的代码：

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");
    }

};

Answer 1

乍一看，您的深度优先搜索(假设DFS应该是深度优先)可能实际上不是深度优先，而是广度优先搜索，因为它立即将所有未访问的邻居添加到搜索队列中。我认为您可能需要添加一条中断语句：

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

在注释中，sudeepdino008正确地指出，DFS可以用堆栈实现，但在这种情况下，我认为在从堆栈中删除顶点之前，不应该将其标记为已访问：

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

问题是:考虑一个简单的图

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

使用原来的算法，顶点将按(3,2,1)顺序而不是(2,3,1)顺序添加到(2,3,1)中。这意味着，在算法的第二部分中，当执行反向BFS时，将在2之前选择3，并且算法将错误地输出(2,3)是一个强连接组件。