0

グラフが強く接続されたコンポーネントであるかどうかを確認するためのこのコードがあります

vector<int> G[2005];
int depth = 0;
void dfs(int u)
{
 visited[u] = 1;
 low[u] = ++depth;
  for(int i=0;i<G[u].size();++i)
  {
    int v = G[u][i];
    if(!visited[v])
        dfs(v);
        low[u] = min(low[u],low[v]);
  }
}

私は dfs(1) を実行し、すべての頂点について、すべての頂点とすべての頂点が訪問された場合に low[u] == 1 かどうかを確認しました。これは正しいアプローチですか？あるはずですが、どういうわけか機能していません。これは私が達成しようとしていることに関する問題ですhttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=2938&mosmsg=Submission+received+with+ID+12516894

4

1 に答える 1

2

Tarjan のアルゴリズムを使用します。

基本的に、時間内に強く接続されたコンポーネントを計算しO(|E|)ます。次に、単純に SCC の数を確認できます。1 でない場合、グラフ全体が 1 つの SCC ではありません。また、早期終了バージョンを提供することもできます。たとえば、2 番目の SCC 終了を見つけた場合などです。

出発点としてのいくつかのC ++：（ただし、それでも疑似コードのようなもの）

vector<SCC> ComputeSCC(Graph& g) {
  int index = 0;
  vector<SCC> sccs;
  stack<Vertex> s;

  //for each vertex grab the SCC
  for(auto v : g.vertices())
    if(v.index == -1)
      StronglyConnected(g, v, index, s, sccs);

  return sccs;
}

void StronglyConnected(Graph& g, Vertex& v, int& i, stack<Vertex>& s, vector<SCC>& sccs) {
  v.index = i;
  v.lowlink = i;
  i++;
  s.push_back(v);

  //for each successor
  for(auto e : v.successors()) {
    if(e.target().index == -1) {
      StronglyConnected(g, e.target(), i, sccs);
      v.lowlink = min(v.lowlink, e.target().lowlink);
    }
    else
      v.lowlink = min(v.lowlink, e.target().index);
  }

  //If v is a root node, pop the stack and generate an SCC
  if(v.lowlink == v.index) {
    sccs.push_back(SCC());
    Vertex w;
    do {
      w = S.pop();
      sccs.back().push_back(w);
    } while(w != v);
  }
}
于 2013-10-17T16:10:11.723 に答える