无向图的割点

一 割点判定法则

如果x不是根节点，则 x 是割点，当且仅当在搜索树上存在 x 的一个子节点 y，满足 low[y]>=dfn[x],若 x 是割点，当且仅当在搜索树上至少存在两个子节点，满足 low[y]>=dfn[x]。

也就是说，如果不是根，且孩子的 low 值大于或等于自己的 dfn 值，则该节点就是割点；如果是根，则至少需要两个孩子满足条件。在下图中，5的子节点是7，满足 low[7] > low[5],因此 5 是割点。

二 割点判定情况

1 不是割点

1不是割点：1是根，只有一个孩子满足 low{2}>dfn[1]

2 割点是根的情况

1是割点：1是根，有两个孩子满足 low{2}>dfn[1]，low[3]>dfn[1]

3 割点不是根的情况

2和3是割点：low[3]>dfn[2],low[4]=dfn[3]

三 代码

package graph.targancut;

import java.util.Scanner;

public class TarjanCut {
    static final int maxn = 1000 + 5;
    static int n;
    static int m;
    static int head[];
    static int cnt;
    static int root;
    static int low[];
    static int dfn[];
    static int num;
    static Edge e[] = new Edge[maxn << 1];

    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new Edge();
        }
    }

    static void add(int u, int v) { // 添加一条边u--v
        e[++cnt].next = head[u];
        e[cnt].to = v;
        head[u] = cnt;
    }

    static void tarjan(int u, int fa) { //求割点
        dfn[u] = low[u] = ++num;
        int count = 0;
        for (int i = head[u]; i != 0; i = e[i].next) {
            int v = e[i].to;
            if (v == fa)
                continue;
            if (dfn[v] == 0) {
                tarjan(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] >= dfn[u]) {
                    count++;
                    if (u != root || count > 1) {
                        System.out.println(u + "是割点");
                    }
                }
            } else
                low[u] = Math.min(low[u], dfn[v]);
        }
    }

    static void init() {
        head = new int[maxn];
        low = new int[maxn];
        dfn = new int[maxn];
        cnt = num = 0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        init();
        int u, v;
        while (m-- > 0) {
            u = scanner.nextInt();
            v = scanner.nextInt();
            add(u, v);
            add(v, u);
        }
        for (int i = 1; i <= n; i++)
            if (dfn[i] == 0) {
                root = i;
                tarjan(1, 0);
            }

    }
}


class Edge {
    int to;
    int next;
}

四 测试

绿色为输入，白色为输出。