c++ - Kosaraju 的 spoj 底部算法

Question

我正在尝试解决 http://www.spoj.com/problems/BOTTOM/

以下是我要执行的步骤:

1) 使用 Kosaraju 算法找到强连通分量。 2) 考虑一个强连接的组件。考虑一条边 u。现在考虑从 u 到某个顶点 v 的所有边。如果 v 位于某个其他 SCC 中，则消除整个强连接分量。否则包括解决方案中的所有元素。

但是，我不断地得到 WA。请帮忙。

这是我的代码:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <fstream>
#include <iterator>
#include <queue>
using namespace std;
int k = 0;
int V, E;
bool fix[5001];
bool fix2[5001];
int compNum[5001];

void dfs(int v, vector< vector<int> >&G, bool *fix, vector <int> &out) {
    fix[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
        int u = G[v][i];
        if (!fix[u]) {
            fix[u] = true;
            dfs(u, G, fix, out);
        }
    }
    out.push_back(v);
}

void dfs2(int v, vector< vector<int> >&G, bool *fix2, vector < vector<int> > &components) {
    fix2[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
        int u = G[v][i];
        if (!fix2[u]) {
            fix2[u] = true;
            dfs2(u, G, fix2, components);
        }
    }
    components[k].push_back(v);
    compNum[v] = k;
}

int main() {
    int a, b;

    while (true) {

        cin >> V; if (V == 0) break; cin >> E;
        vector< vector<int> >G(V + 1);
        vector< vector<int> >G2(V + 1);

        vector<int>out;
        vector < vector<int> >components(V + 1);


        for (int i = 0; i < E; i++) {
            cin >> a >> b;
            G[a].push_back(b);
            G2[b].push_back(a);
        }



        for (int i = 1; i <= V; i++) {
            if (!fix[i])
                dfs(i, G, fix, out);
        }

        reverse(out.begin(), out.end());

        for (int i = 0; i < out.size(); i++){
            if (!fix2[out[i]]) {
                dfs2(out[i], G2, fix2, components);
                k++;
            }
        }

        vector<int>gamotana;

        for (int i = 0; i < components.size(); i++) {
            for (int j = 0; j < components[i].size(); j++) {
                bool check = true;
                for (int z = 0; z < G[components[i][j]].size(); z++)
                {
                    if (compNum[G[components[i][j]][z]] != i)
                    {
                        check = false; goto next123;
                    }
                }
                if (check)
                    gamotana.push_back(components[i][j]);
            }
        next123:;
        }

            sort(gamotana.begin(), gamotana.end());

        for (int i = 0; i < gamotana.size(); i++)
            cout << gamotana[i] << " ";

        for (int i = 0; i < 5001; i++) {
            fix[i] = false;
            fix2[i] = false;
            compNum[i] = -1;
        }
        k = 0;

        cout << endl;
    }

    return 0;

}

Answer 1

在您的算法描述中，您说如果某条边通向不同的组件，您将消除整个连接的组件。

但是，在您的代码中，您似乎将组件 i 中的所有顶点 j 添加到您的解决方案中，直到找到引出的边。换句话说，即使组件不是汇点，您仍然可能会错误地将某些顶点报告为汇点。

我想你应该做更像这样的事情:

    for (int i = 0; i < components.size(); i++) {
        for (int j = 0; j < components[i].size(); j++) {

            for (int z = 0; z < G[components[i][j]].size(); z++)
            {
                if (compNum[G[components[i][j]][z]] != i)
                {
                    goto next123;
                }
            }
        }

        for (int j = 0; j < components[i].size(); j++)
            gamotana.push_back(components[i][j]);

    next123:;
    }

当然，可能还有更多的问题。我会建议您首先尝试构建和测试一些小示例，然后可能会针对强力求解器进行测试以识别失败案例。