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，那么整个图不是一个 SCC。此外，您可以提供一个提前退出版本，例如，一旦我发现第二个 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 回答