tarjan算法

tarjan 算法（Tarjan’s strongly connected components algorithm）

很棒的解释视频

简述算法

Tarjan 算法是一种用于查找图中强连通分量的算法，由 Robert Tarjan 在 1972 年提出。强连通分量是指在有向图中，如果从顶点 u 到顶点 v 以及从顶点 v 到顶点 u 都存在一条路径，那么顶点 u 和顶点 v 是强连通的。

Tarjan 算法的核心思想是通过深度优先搜索（DFS）遍历图，并使用堆栈来追踪搜索过程中的顶点。在遍历的过程中，对每个顶点进行标记，记录其在搜索树中的深度和最小后向边的深度。如果发现某个顶点的后继节点指向了一个已经被访问过的顶点，那么这个顶点及其所有后继节点构成一个强连通分量。

Tarjan 算法的关键点在于维护一个栈，用来保存正在搜索的节点。当 DFS 遍历过程中发现一个节点的所有后继节点已经搜索完毕，并且该节点是当前 DFS 搜索树中的根节点时，可以将该节点以及其所有后继节点弹出栈，并将它们标记为一个强连通分量。

Tarjan 算法的时间复杂度为 O(V + E)，其中 V 表示图中的顶点数，E 表示图中的边数。由于只需要一次 DFS 遍历即可找到所有的强连通分量，因此 Tarjan 算法是一种高效的强连通分量查找算法。

个人理解

首先什么是强连通分量。就是有向图中一些点，如果每两个点之间互相都有一条到达对方的道路，那么这些点就组成了强连通分量（Strongly Connected Component，简称 SCC）。

我们可以想象为每一个SCC就是一个家庭，如果送报纸的话只需要给家庭中任意一个人就行了，因为他们每个人都可以在看完报纸后递给另一个家人。显然我们可以进行缩点了。从之前人与人之间的联系上升到家庭与家庭之间的关系。但是因为是有向图，SCC之间可能有边相连，但是是单向的，所以家庭之间并不能合并为同一个SCC。但是在一个家庭所有成员读完报纸后可以委托一个有出边的人去把报纸给邻居（另一个SCC）。

算法实现

在此并不证明算法的正确性。现在只聊一聊算法是怎么实现的。

首先就是dfn[]和low[]数组。对于图的遍历选择dfs（Depth-First Search）。dfn[]数组记录遍历点的次序。通常为每遍历到一个点，计数器+1，此点的dfn值即为计数器的值。而low[]数组则为记录该点以及其子节点最小的dfn值。

如果我们想要知道每个SCC中成员都有谁，那么我们需要在遍历点的同时再将点压入栈stack s内。同时我们需要知道该点是否在栈内，定义一个记录数组onStack[],如果节点i在栈内，那么onStack[i]=1。如果点的标值不是从1~n连续的，可能需要hash处理。

那么我们在回过头讨论dfn和low。对于不在栈内的节点，我们直接low[u]=min(low[u],low[v])进行更新。其中u为当前节点，v为u的子节点。对于已经在栈内的子节点，我们通过low[u]=min(low[u],dfn[v])更新。我们可以想象有向图中边一直往前冲，突然有一个边是往回走的，这样就会连接到刚才已经遍历过的点（可能形成一个环），但是这种边我们需要判断是否连接到了另一个SCC，所以我们需要记录点是否在栈内，如果在栈内说明两个点属于同一个SCC，所以可以更新，如果不在，就不能更新当前点的low值。

数据出栈。对于遍历完所有子节点的点来说，如果dfn[u]==low[u]那么说明这是一个SCC。栈内点一个个出栈直到当前点出栈，出栈的所有点即为一个SCC的所有点。定义sccs[]数组记录点所属于的SCC。

代码实现

java

摘自github

/**
 * An implementation of Tarjan's Strongly Connected Components algorithm using an adjacency list.
 *
 * <p>Verified against:
 *
 * <ul>
 *   <li>https://open.kattis.com/problems/equivalences
 *   <li>https://open.kattis.com/problems/runningmom
 *   <li>https://www.hackerearth.com/practice/algorithms/graphs/strongly-connected-components/tutorial
 * </ul>
 *
 * <p>Time complexity: O(V+E)
 *
 * @author William Fiset, [email protected]
 */
package com.williamfiset.algorithms.graphtheory;

import static java.lang.Math.min;

import java.util.*;

public class TarjanSccSolverAdjacencyList {

  private int n;
  private List<List<Integer>> graph;

  private boolean solved;
  private int sccCount, id;
  private boolean[] visited;
  private int[] ids, low, sccs;
  private Deque<Integer> stack;

  private static final int UNVISITED = -1;

  public TarjanSccSolverAdjacencyList(List<List<Integer>> graph) {
    if (graph == null) throw new IllegalArgumentException("Graph cannot be null.");
    n = graph.size();
    this.graph = graph;
  }

  // Returns the number of strongly connected components in the graph.
  public int sccCount() {
    if (!solved) solve();
    return sccCount;
  }

  // Get the connected components of this graph. If two indexes
  // have the same value then they're in the same SCC.
  public int[] getSccs() {
    if (!solved) solve();
    return sccs;
  }

  public void solve() {
    if (solved) return;

    ids = new int[n];
    low = new int[n];
    sccs = new int[n];
    visited = new boolean[n];
    stack = new ArrayDeque<>();
    Arrays.fill(ids, UNVISITED);

    for (int i = 0; i < n; i++) {
      if (ids[i] == UNVISITED) {
        dfs(i);
      }
    }

    solved = true;
  }

  private void dfs(int at) {
    ids[at] = low[at] = id++;
    stack.push(at);
    visited[at] = true;

    for (int to : graph.get(at)) {
      if (ids[to] == UNVISITED) {
        dfs(to);
      }
      if (visited[to]) {
        low[at] = min(low[at], low[to]);
      }
      /*
       TODO(william): investigate whether the proper way to update the lowlinks
       is the following bit of code. From my experience this doesn't seem to
       matter if the output is placed in a separate output array, but this needs
       further investigation.

       if (ids[to] == UNVISITED) {
         dfs(to);
         low[at] = min(low[at], low[to]);
       }
       if (visited[to]) {
         low[at] = min(low[at], ids[to]);
       }
      */

    }

    // On recursive callback, if we're at the root node (start of SCC)
    // empty the seen stack until back to root.
    if (ids[at] == low[at]) {
      for (int node = stack.pop(); ; node = stack.pop()) {
        visited[node] = false;
        sccs[node] = sccCount;
        if (node == at) break;
      }
      sccCount++;
    }
  }

  // Initializes adjacency list with n nodes.
  public static List<List<Integer>> createGraph(int n) {
    List<List<Integer>> graph = new ArrayList<>(n);
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    return graph;
  }

  // Adds a directed edge from node 'from' to node 'to'
  public static void addEdge(List<List<Integer>> graph, int from, int to) {
    graph.get(from).add(to);
  }

  /* Example usage: */

  public static void main(String[] arg) {
    int n = 8;
    List<List<Integer>> graph = createGraph(n);

    addEdge(graph, 6, 0);
    addEdge(graph, 6, 2);
    addEdge(graph, 3, 4);
    addEdge(graph, 6, 4);
    addEdge(graph, 2, 0);
    addEdge(graph, 0, 1);
    addEdge(graph, 4, 5);
    addEdge(graph, 5, 6);
    addEdge(graph, 3, 7);
    addEdge(graph, 7, 5);
    addEdge(graph, 1, 2);
    addEdge(graph, 7, 3);
    addEdge(graph, 5, 0);

    TarjanSccSolverAdjacencyList solver = new TarjanSccSolverAdjacencyList(graph);

    int[] sccs = solver.getSccs();
    Map<Integer, List<Integer>> multimap = new HashMap<>();
    for (int i = 0; i < n; i++) {
      if (!multimap.containsKey(sccs[i])) multimap.put(sccs[i], new ArrayList<>());
      multimap.get(sccs[i]).add(i);
    }

    // Prints:
    // Number of Strongly Connected Components: 3
    // Nodes: [0, 1, 2] form a Strongly Connected Component.
    // Nodes: [3, 7] form a Strongly Connected Component.
    // Nodes: [4, 5, 6] form a Strongly Connected Component.
    System.out.printf("Number of Strongly Connected Components: %d\n", solver.sccCount());
    for (List<Integer> scc : multimap.values()) {
      System.out.println("Nodes: " + scc + " form a Strongly Connected Component.");
    }
  }
}

C++

对应洛谷题目
如果SCC之间有边相邻，只需通知一个SCC即可。

#include<bits/stdc++.h>
using namespace std;
const int mxlen = 5e5 + 10;
int n,m;
int pre[mxlen],last[mxlen/5],other[mxlen],l;
int cnt,sccCount;
int dfn[mxlen/5],low[mxlen/5],onStack[mxlen/5];
int sccFlags[mxlen/5];
int sccIndice[mxlen/5];
stack<int> s;
void add(int x,int y){
    l++;
    pre[l]=last[x];
    last[x]=l;
    other[l]=y;
}
void tarjan(int x){
    cnt++;
    dfn[x]=low[x]=cnt;
    onStack[x]=1;
    s.push(x);
    for(int p=last[x];p;p=pre[p]){
        int y=other[p];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(onStack[y]){
            low[x]=min(low[x],dfn[y]);
        } 
    }
    if(dfn[x]==low[x]){
        sccCount++;
        while(s.top()!=x){
            sccIndice[s.top()]=sccCount;
            onStack[s.top()]=0;
            s.pop();
        }
        sccIndice[x]=sccCount;
        onStack[x]=0;
        s.pop();
    }
}
void checkPropagation(){
    for(int i=1;i<=n;i++){
        for(int p=last[i];p;p=pre[p]){
            int y=other[p];
            if(sccIndice[i]!=sccIndice[y]){
                sccFlags[sccIndice[y]]=1;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin >> x >> y;
        add(x,y);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    checkPropagation();
    int ans=0;
    for(int i=1;i<=sccCount;i++){
        if(!sccFlags[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}