tarjan 求 强连通分量模板割点 + 链式前向星

Expert_Dream · 2023-07-20 14:47:42 · 个人记录

Tarjan

抽象难懂的算法

第一次接触链式前向星，本算法储存方式为链式前向星，用vector不香吗

神犇的blog

通俗易懂的讲解

通俗题解

抽象难懂的讲解

P1656题解-生动形象讲解割边

模板代码中富含丰富的注释

// P3388 AC code
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl "\n"
using namespace std;
int n,m;
const int N = 2e4+5;
vector<int> mp[N];//存图
int vis[N];//每个点访问标记
int ans[N];//是否是割点
int id,res;//id是时间戳,res为割点数量
int low[N];
int dfn[N];//每个结点的时间戳也就是id
void tarjan(int x,int fa){
    vis[x]=1;
    low[x]=dfn[x]=++id;
    int son=0;//此节点的儿子数量
    for(auto it:mp[x]){
        if(!vis[it]){
            //儿子
            son++;
            tarjan(it,x);//遍历在先
            low[x] = min(low[x],low[it]);
            if(fa!=x && low[it] >= dfn[x] && !ans[x]){//根据定义的判断方式
                ans[x] = 1;res++;//是割点
            }
        }else if(it != fa){
            low[x] = min(low[x],dfn[it]);
        }
    }
    if(fa==x && son >= 2 && !ans[x]){
        //根节点--
        ans[x]=1;
        res++;      
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        int a,b;
        cin >> a >> b;
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    for(int i = 1;i <= n;i++){
        if(vis[i]==0){
            id =0 ;
            tarjan(i,i);
        }
    }
    cout<<res<<endl;
    for(int i = 1;i <= n;i++){
        if(ans[i]) cout<<i<<" ";
    }
    return 0;
}