SPOJ底部的强连接部件

Question

然而，我不断得到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