1

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

};
4

1 に答える 1

2

一見すると、深さ優先検索 (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

元のアルゴリズムでは、頂点はではなくnodesの順序で追加されます。これは、アルゴリズムの 2 番目の部分で、後方 BFS が実行されるときにが前に選択されることを意味し、アルゴリズムは が強連結成分であると誤って出力します。(3,2,1)(2,3,1)23(2,3)

于 2013-10-01T18:53:25.680 に答える