此博客为补档博客,只做简单讲解。

求解方法比较简单,考虑维护两个数组 tinlow,分别表示进来的节点进入递归的时间戳和其树边构成的连通块可以到达的时间戳最小的节点。

如果遇到了一个节点 $u$,满足 $tin(u)=low(u)$,意味着其子树内为一个强联通分量,读者可以自行画图证明。

时间复杂度 $\mathcal O(n)$。

代码实现

void tarjan(int u) {
  tin[u] = low[u] = ++dfc;
  inStack[u] = 1;
  stk[++top] = u;
  for (auto v : g[u]) {
    if (!tin[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (inStack[v]) {
      low[u] = min(low[u], tin[v]);
    }
  }
  if (tin[u] == low[u]) {
    scc++;
    int v = 0;
    do {
      v = stk[top--];
      inStack[v] = 0;
      bel[v] = scc;
    } while (v != u);
  }
}

而 Tarjan 求强联通分量一般处理的是强连通的节点有共同的性质的问题,缩点后我们得到了一个 DAG,就不需要考虑环的情况,可以把复杂问题简单化,以及优化时间复杂度和常数。

最后修改:2020 年 08 月 30 日 12 : 23 AM
如果觉得我的文章对你有用,请随意赞赏