kosaraju算法對SPOJ屁股

Question

我試圖解決http://www.spoj.com/problems/BOTTOM/

這裏是我下面的步驟：

1）找到使用kosaraju算法強連通分量。 2）考慮一個強連通的組件。考慮一下你的優勢。現在考慮從u到某些vertice 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:; 
    } 

當然，可能會有更多的問題。我會建議你先嚐試構建和測試一些小例子，或者用一個蠻力解決方案進行測試來識別失敗的案例。