P3388- tarjan算法

初识tarjan算法，还要从一道算法考试题说起，当时没有听过这个算法，当然是铩羽而归

我理解的tarjan算法：

基础为dfs的思想，从根节点（可以是任意一个点）开始，递归的每个点，都按照访问顺序赋予编号，我们用dfn[]数组表示，

同时我们记录这些点的深度，用low[]数组表示

在dfn探索的过程中，我们需要不断更新low[]数组，为什么要更新？如何更新呢？

首先我们看第一个问题，为什么要更新，low[]数组存的是深度，啥的深度呢？具体来讲应该是该点辈分最高的祖先深度（既深度最浅）。

存这个意义是啥呢？ 假设一个点u不是根节点，也不是叶子节点，u的子节点为v。当low[v]>=dfn[u]时，说明啥？

说明要想到达v这个点，必须经过u，那么u就必然是割点。倘若low[v] < dfn[u],就说明之前已经有一个辈分更高的祖先访问到了v,此时无法判断u是否为割点。

---所有的叶子节点必然不是割点

---那么如何判断根节点呢？ 很简单，只需要记录根节点的分支即可，当分支>=2时，必然为割点。

那我们回到刚才的问题，如何更新low[]呢？在某一个分支递归完之前按： low[u] = Math.min(low[u], low[v]); 之后：low[u] = Math.min(low[u], dfn[v]);

代码实现如下：其中的线程是为了跑过这个题单加的。可以忽略。

package com.Vjudge;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
// 割点模板题目
public class P3388_tarjan implements Runnable {
    @Override
    public void run() {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        try {
            st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
            e.printStackTrace();
        }
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        dfn = new int[maxn]; // 访问顺序存储数组
        low = new int[maxn]; // 访问父节点
        cnt = new int[maxn];
        edges = new Edge[2*maxm];
        head = new int[maxn];
        Arrays.fill(head, -1);
        numb = 0;
        for (int i = 0; i < m; i++) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            add(x, y);
            add(y, x);
        }
        num = 0;
        for (int i = 1; i <= n; i++) {
            if(dfn[i] == 0) { // 如果当前点没有被访问就开始寻找割点
                root = i; // 起始点为根节点
                tarjan(i);
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if(cnt[i] == 1) ans++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if(cnt[i] == 1) sb.append(i+" ");
        }
        System.out.println(ans);
        System.out.println(sb.toString());
    }
    // 链式向前星边的实例
    static class Edge {
        int to;
        int next;
        public Edge(int to, int next) {
            this.to = to;
            this.next = next;
        }
    }
    // dfn 存储无向图的访问顺序的编号
    // low[u]表示顶点u及其子树中的点，通过非父子边（回边），能够回溯到的最早的点（dfn最小）的dfn值（但不能通过连接u与其父节点的边）
    // cnt[u]用来记录u点是割点
    // head 链式向前星的数据结构数组
    private static int[] dfn, low, cnt, head;
    // root 全局根节点，用来判断根节点是不是割点
    // num 访问顺序编号全局变量
    // n 图中点的个数
    // m 图中边的个数
    // numb 链式向前星边的编号
    private static int root, num, n, m, numb;
    private static Edge[] edges;
    private static int maxn = 100010, maxm = 500010;
    // 添加边
    private static void add(int u, int v) {
        edges[numb] = new Edge(v, head[u]);
        head[u] = numb++;
    }
    public static void main(String[] args) throws Exception {
        new Thread(null, new P3388_tarjan(), "", 1 << 29).start();
    }
    private static void tarjan(int u) {
        dfn[u] = low[u] = ++num; // 访问顺序初始化时 dfn和low一样
        int count = 0; // 计算跟节点的分支
        // 链式向前星遍历边的编号
        for (int n = head[u]; n != -1 ; n = edges[n].next) {
            int v = edges[n].to;
            if(dfn[v] == 0) { // 没有被访问
                count++;     // 根节点分支加一
                tarjan(v);  // 深度搜索
                // 找到最底层回溯进行更新当前u点的low值，当前点low和回溯子节点low取小
                low[u] = Math.min(low[u], low[v]);
                // 如果u是根节点，并且 根节点的分支大于1 说明根节点是割点，进行标记
                // 如果u不是根节点，但是u的dfn小于子节点的 low值， 说明走向子节点v必须经过父节点u，所以父节点是割点
                if((u == root && count > 1) || (u != root && dfn[u] <= low[v])) {
                    cnt[u] = 1;
                }
            }
            // 如果找到最底部已经被访问过，更新当前点的low通过回溯边的 dfn比较
            low[u] = Math.min(low[u], dfn[v]);
        }
    }
}

原文：https://www.cnblogs.com/bryant-kun/p/13856225.html