无向图的Tarjan算法（割边与割点）

书P394~399

1、割边判定
模版题:P1656 https://www.luogu.com.cn/problem/P1656

#include <bits/stdc++.h>
using namespace std;
const int SIZE=100010;
int head[SIZE],ver[SIZE*2],Next[SIZE*2];
int dfn[SIZE],low[SIZE];
bool bridge[SIZE*2];
int n,m,tot,num;
struct abc
{
    int u,v;
};
bool cmp1(abc f1,abc f2)
{
    if(f1.u==f2.u)
    {
        return f1.v<f2.v;
    }
    return f1.u<f2.u;
}
void add(int x,int y)
{
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int x,int in_edge)
{
    dfn[x]=low[x]=++num;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x])
            {
                bridge[i]=bridge[i^1]=true;
            }
        }
        else if(i!=(in_edge^1))
            low[x]=min(low[x],low[y]);
    }
}
int main()
{
    cin>>n>>m;
    tot=1;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])    tarjan(i,0);
    }
    vector<abc> bian;
    for(int i=2;i<tot;i+=2)
    {
        if(bridge[i])
        {
            abc r;
            r.u=min(ver[i^1],ver[i]);
            r.v=max(ver[i^1],ver[i]);
            bian.push_back(r);
        }
    }
    sort(bian.begin(),bian.end(),cmp1);
    for(int i=0;i<bian.size();i++)
    {
        cout<<bian[i].u<<" "<<bian[i].v<<endl;
    }
    return 0;
}

2、割点判定

#include <bits/stdc++.h>
using namespace std;
const int SIZE=100010;
int head[SIZE],ver[SIZE*2],Next[SIZE*2];
int dfn[SIZE],low[SIZE];//,stack[SIZE];
bool cut[SIZE*2];
int n,m,tot,num,root;
void add(int x,int y)
{
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++num;
    int flag=0;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x])
            {
                flag++;
                if(x!=root||flag>1)    cut[x]=true;
            }
        }
        else    low[x]=min(low[x],dfn[y]);
    }
}
int main()
{
    cin>>n>>m;
    tot=1;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        if(x==y)    continue;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            root=i;
            tarjan(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(cut[i]==true)
        {
            cout<<i<<endl;
        }
    }
    return 0;
}

参考笔记：https://blog.csdn.net/qq_39670434/article/details/81570157