割点算法

割点算法Tarjan

割点算法 引入了建立在DFS生成树的遍历节点的时间戳概念,如果一个节点u的子节点v可以找到一条不经过u以外的路径到达u的祖先,那么显然有一条通路可以回到u的祖先。反之,如果存在v找不到这么一条路径回到u的祖先,那么显然u是一个割点,他分割了v所在的子树和其他子树(如果u不是根的话,包括祖先所在子树)。

image-20210509113600747

那么一个割点有多少子树呢?
首先,一个割点的对应的v是独立在各个子树的吗?是的,如果存在v1v2都找到路径,且在一个子树中,那么必然有v1可以通过v2找到u,那么在DFS搜索的时候,必定会一次遍历v1v2。所以每个割点对应的子树只会搜索到一个v
扩展一下, 那么经过去掉割点的图最多有几个连通块?

POJ 2117 Electricity

参考解答


#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int N = 10005;
const int M = 30005;
int tot;
int to[M], nxt[M], head[M]; // graph 链式前向星存储方式
int dfn[N];
int low[N];
int ts;
int n, m;
int bp, cnt;
int root;
void add(int u, int v){ // connstruct graph;
    ++tot;
    to[tot] = v;
    nxt[tot] = head[u];
    head[u] = tot;
}
void tarjan(int u){
    // cout << u << ' '; 
    int subtree = 0;
    dfn[u] = low[u] = ++ts;
    for(int i = head[u]; i; i = nxt[i]){
        int v = to[i];
        
        if(dfn[v]) low[u] = min(low[u], dfn[v]);
        else{
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) ++subtree;; // 节点u是割点,且割点对应的子节点v是在一个被分割子树中
        }
    }
    if( u != root) ++subtree;
    bp = max(bp, subtree);
}
int main(){
    while(scanf("%d%d", &n, &m), n || m){
        ts = tot = bp = cnt = 0;
        memset(head, 0x00, sizeof head); // to 和 edge 不需要重置
        memset(dfn, 0x00, sizeof dfn);
        memset(low, 0x00, sizeof low);
        int a ,b;
        while(m--){
            scanf("%d%d", &a, &b);
            add(a, b);
            add(b, a);            
        }
        
        for(root = 0; root < n; ++root){
            if(!dfn[root]){
                tarjan(root);
                cnt++;
            }
        }
        printf("%d\n", cnt + bp - 1);
    }
    return 0;
}   


补充知识点

前向星不过是把边按出发点排序并顺序存储下来, 通过记录首部位置来遍历;
链式前向星更进一步,通过在头部位置记录边的地点,同时以静态方式存储边,在静态边中存储下下条边的地址。

最后还有常用的对拍程序:

#!/bin/sh
g++ $1 -o ./a.out 
./a.out < input  > myoutput
diff myoutput output -s -u

Comments