c++ - 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 应该是深度优先的)可能实际上不是深度优先的，而是广度优先搜索，因为它添加了所有未访问的立即搜索队列的邻居。我认为您可能需要添加一个 break 语句:

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)添加到节点 。这意味着，在算法的第二部分，当执行反向 BFS 时，2 将在 3 之前被选择，算法将错误地输出 (2,3) 是强连通分量。