题解：P3388 【模板】割点（割顶）

· · 题解

简介：

一种由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。

代码：

割点（割顶）:

理解1：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define x first
#define y second
const int mod=1e9+7;
const int N=2e4+50;
const int M=1e5+50;
#define endl '\n'
//#define int ll
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int head[N]; 
struct edge{
    int u,v,nxt;
}e[M<<1];
int n,m;
int tot=0;
bool is_cut[N]={}; 
void add_edge(int u,int v){ //链式前向星建边
    e[++tot]=edge{u,v,head[u]};
    head[u]=tot;
}
int id=0; //表示时间戳
//low 表示在 u 的子树中能够回溯到的最早的已经在栈中的结点，更简单点讲就是表示这个点双路(无重复点)的最小时间戳
int dfn[N]={},low[N]={}; //dfn 表示这个节点的时间戳
void tarjan(int u,int root){  //Tarjan 算法函数
    int cnt=0; //cnt 表示 u 这个点的子节点
    dfn[u]=low[u]=++id; //表示初始化，都初始化为时间戳
    for(int i=head[u];i;i=e[i].nxt){ //遍历每一条边
        int v=e[i].v; //表示每一条边的终点
        if(!dfn[v]){ //如果是一个新的节点
            cnt++; //+1
            tarjan(v,root); //递归，进行初始化
            low[u]=min(low[u],low[v]); //比较最小时间戳
            if(u!=root&&dfn[u]<=low[v]){ 
                //如果说 u 节点不是 root 节点,并且 dfn[u]<=low[v]，就说明 v 节点和它的祖先之间的路线必有 u 节点，也就进一步说明 u 节点是一个割点
                is_cut[u]=1; //标记为割点
            }
        }else{
            low[u]=min(low[u],dfn[v]); //否则，就说明 v 节点是 u 节点的祖先，而且因为 v 节点已被访问，所以只能跟 dfn[v] 比最小时间戳
        }
    } 
    if(u==root&&cnt>1){ //判断，如果 u 节点是根节点，且有大于 1 个的子节点的话，就能成为割点
        is_cut[u]=1; //标记
    }
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  IO;
    cin>>n>>m; //输入
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        add_edge(x,y); //连边
        add_edge(y,x);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){ 
            //判断，如果这个节点没有在上个联通块遍历的时候添加时间戳，就说明这个节点所处的是一个新的联通块，因为是首次发现这个新的联通块，所以就从这个点开始，遍历这个新的联通块，并且把这个点作为这个新联通块的根节点
            tarjan(i,i); //遍历这个新的联通块
        } 
    }
    int ans=0; //表示割点的个数
    for(int i=1;i<=n;i++){
        if(is_cut[i]==1){ //判断
            ans++; //+1
        } 
    }
    cout<<ans<<endl; //输出
    for(int i=1;i<=n;i++){
        if(is_cut[i]==1){ //判断
            cout<<i<<" "; //输出
        }
    }
    return 0;
}
//参考题目:https://www.luogu.com.cn/problem/P3388

理解2：

其实，我们还可以用另外一种理解方式：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define x first
#define y second
const int mod=1e9+7;
const int N=1e5+50;
#define endl '\n'
//#define int ll
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,m;
struct edge{ //链式前向星建边
    int u,v,nxt;
}e[N<<1];
int head[20005]={}; 
int tot=0;
void addedge(int u,int v){ //插入一条边
    e[++tot]=edge{u,v,head[u]};
    head[u]=tot;
}
int dfn[20005]={},low[20005]={};
//dfn[i] 是按照 dfs 序的到第 i 个点的时间戳，low[i] 表示第 i 个点在双路(无重复点)的前提下能到达的最小时间戳
int is_cut[20005]={}; //is_cut[i] 表示第 i 个点是否是割点
int id=0;
void tarjan(int u,int root){ //Tarjan 算法函数
    int cnt=0; //表示我 u 节点有多少个孩子
    dfn[u]=low[u]=++id; //初始化，low[u] 最坏情况下也是自己本身的时间戳
    for(int i=head[u];i;i=e[i].nxt){ //遍历边
        int v=e[i].v;
        if(!dfn[v]){ //如果 v 是 u 的孩子的话
            cnt++; //+1
            tarjan(v,root); //递归
            low[u]=min(low[u],low[v]); //原理请看下方，①
            if(u!=root&&low[v]>=dfn[u]){ //如果说low[v]>=dfn[u] 就是说 v 无法在双路(无重复点)的前提下能到达 u 的上面，说明 v 到 u 的上面必须要经过 u 点，那么也就说明 u 点就是割点
                is_cut[u]=1; //标记
            }
        }else{
            low[u]=min(low[u],dfn[v]);//原理请看下方，②
        }
    }
    if(u==root&&cnt>1){ //原因请看下方，③
        is_cut[u]=1; //标记
    }
} 
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  IO;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        addedge(u,v);
        addedge(v,u);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            //判断，如果这个节点没有在上个联通块遍历的时候添加时间戳，就说明这个节点所处的是一个新的联通块，因为是首次发现这个新的联通块，所以就从这个点开始，遍历这个新的联通块，并且把这个点作为这个新联通块的根节点
            tarjan(i,i); //遍历这个新的联通块
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(is_cut[i]==1){
            ans++; //+1
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++){
        if(is_cut[i]==1){
            cout<<i<<" ";
        }
    }
    return 0;
}
/*
参考题目:https://www.luogu.com.cn/problem/P3388
*/