tarjan无向图求桥与割点

边的双连通分量，求桥！ 点的双连通分量，求割点！

点的双连通分量
#include <bits/stdc++.h>
using namespace std;

const int N = 4e6+9;
int n,m;
int numE,head[N];
int root,dfn[N],low[N];
int timestamp,stk[N];
int top,dcc_cnt;
bool cut[N];
vector<int> dcc[N];
struct E {
    int next,to;
}e[N];

void add(int a,int b) {
    e[numE] = {head[a],b};
    head[a] = numE++;
}

inline void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u;
    if(u == root && head[u] == -1) {
        dcc_cnt++;
        dcc[dcc_cnt].push_back(u);
        return;
    }
    int flag = 0;
    for(int i=head[u]; ~i; i=e[i].next) {
        int v = e[i].to;
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u],low[v]);
            if(dfn[u] <= low[v]) {
                flag++;
                if(u != root || flag > 1) cut[u] = true;
                ++dcc_cnt;
                int y;
                do {
                    y = stk[top--];
                    dcc[dcc_cnt].push_back(y);
                } while(y != v);
                dcc[dcc_cnt].push_back(u);
            }
        } else low[u] = min(low[u],dfn[v]);
    }
    if(flag == 0 && u == root) dcc[++dcc_cnt].push_back(u); //自环根据需求可以删掉！
}

int main() {
    cin >> n >> m;
    memset(head,-1,sizeof head);
    for(int i=1; i<=m; i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    for(int i=1; i<=n; i++) {
        if(!dfn[i]) {
            root = i;
            tarjan(i);
        }
    }
    cout<<dcc_cnt<<"\n";
    for(int i=1; i<=dcc_cnt; i++) {
        printf("%d ",dcc[i].size());
        for(auto v : dcc[i]) {
            printf("%d ",v);
        }
        putchar('\n');
    }
    return 0;
}

//边的双连通分量
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long ll;
const int N = 4e6+9;

vector<int> dcc[N];
int head[N],numE;
int n,m;
struct E {
    int next,to;
}e[N];

int dfn[N],low[N],stk[N],id[N];
int timestamp,dcc_cnt,top;
bool is_bridge[N];

void add(int a,int b) {
    e[numE] = {head[a],b};
    head[a] = numE++;
}

void tarjan(int u,int from) {
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u;
    for(int i=head[u]; ~i; i=e[i].next) {
        int v = e[i].to;
        if(!dfn[v]) {
            tarjan(v,i);
            low[u] = min(low[u],low[v]);
            if(dfn[u] < low[v])
                is_bridge[i] = is_bridge[i ^ 1] = true;
        } else if(i != (from ^ 1)) {
            low[u] = min(low[u],low[v]);
        }
    }
    if(dfn[u] == low[u]) {
        ++dcc_cnt;
        int y;
        do {
            y = stk[top--];
            id[y] = dcc_cnt;
            dcc[dcc_cnt].push_back(y);
        } while(y != u);
    }
}

int main() {
    memset(head,-1,sizeof head);
    cin >> n >> m;
    for(int i=1; i<=m; i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    for(int i=1; i<=n; i++) {
        if(!dfn[i]) {
            tarjan(i,0);
        }
    }
    printf("%d\n",dcc_cnt);
    for(int i=1; i<=dcc_cnt; i++) {
        printf("%d ",dcc[i].size());
        for(auto v : dcc[i]) {
            printf("%d ",v);
        }
        puts("");
    }
    return 0;
}

//无向图e-Dcc的缩点！
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 2e5+9;
int head[N],numE;
int dfn[N],low[N],bridge[N];
int num,Dcc,c[N];
struct Edge
{
    int next,to;
}e[N],ex[N];
void add(Edge e[],int a,int b)
{
    e[numE].next = head[a];
    e[numE].to = b;
    head[a] = numE++;
}
void tarjan(int x,int in_edge)
{
    dfn[x] = low[x] = ++num;
    for(int i=head[x]; ~i; i=e[i].next)
    {
        int y = e[i].to;
        if(!dfn[y])
        {
            tarjan(y,i);
            low[x] = min(low[x],low[y]);
            if(low[y] > dfn[x])
                bridge[i] = bridge[i ^ 1] = 1;
        }
        else if(i != (in_edge ^ 1))
            low[x] = min(low[x],dfn[y]);
    }
}
void dfs(int u)
{
    c[u] = Dcc;
    for(int i=head[u]; ~i; i=e[i].next)
    {
        int v = e[i].to;
        if(c[v] || bridge[i]) continue;
        dfs(v);
    }
}
void solve()
{
    memset(head,-1,sizeof head);
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(e,a,b);
        add(e,b,a);
    }
    for(int i=1; i<=n; i++)
    {
        if(!dfn[i]) tarjan(i,-1);
    }
    for(int i=1; i<=n; i++)
    {
        if(!c[i])
        {
            ++Dcc;
            dfs(i);
        }
    }
    printf("this map have %d dcc\n",Dcc);
    for(int i=1; i<=n; i++)
    {
        printf("i = %d c[i] = %d\n",i,c[i]);
    }
    printf("---------------------------------------\n");
    numE = 0;
    for(int i=0; i<2*m; i++)
    {
        int x = e[i ^ 1].to,y = e[i].to;
        if(c[x] == c[y]) continue;
        printf("x = %d y = %d\n",x,y);
        add(ex,x,y);
    }
    printf("缩点后的图为:\n");
    for(int i=0; i<numE; i+=2)
    {
        printf("%d %d\n",ex[i].to,ex[i ^ 1].to);
    }
}
int main()
{
    solve();
    return 0;
}
//9 11
//1 2
//1 5
//1 6
//2 3
//2 5
//3 4
//5 4
//6 9
//6 8
//8 9
//6 7

//求边的双连通分量！
//1 用搜索删除桥的方式!
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 2e5+9;
int head[N],numE;
int dfn[N],low[N],bridge[N];
int num,Dcc,c[N];
struct Edge 
{
    int next,to;
}e[N];
void add(int a,int b)
{
    e[numE].next = head[a];
    e[numE].to = b;
    head[a] = numE++;
}
void tarjan(int x,int in_edge)
{
    dfn[x] = low[x] = ++num;
    for(int i=head[x]; ~i; i=e[i].next) 
    {
        int y = e[i].to;
        if(!dfn[y]) 
        {
            tarjan(y,i);
            low[x] = min(low[x],low[y]);
            if(low[y] > dfn[x]) 
                bridge[i] = bridge[i ^ 1] = 1;
        }
        else if(i != (in_edge ^ 1)) 
            low[x] = min(low[x],dfn[y]);
    }
}
void dfs(int u) 
{
    c[u] = Dcc;
    for(int i=head[u]; ~i; i=e[i].next)
    {
        int v = e[i].to;
        if(c[v] || bridge[i]) continue;
        dfs(v);
    }
}
void solve()
{
    memset(head,-1,sizeof head);
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=m; i++) 
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    for(int i=1; i<=n; i++) 
    {
        if(!dfn[i]) tarjan(i,-1);
    }
    for(int i=1; i<=n; i++)
    {
        if(!c[i]) 
        {
            ++Dcc;
            dfs(i);
        }
    }
    printf("this map have %d dcc\n",Dcc);
    for(int i=1; i<=n; i++) 
    {
        printf("i = %d c[i] = %d\n",i,c[i]);
    }
}
int main()   
{
    solve();
    return 0;
}

P3388 【模板】割点（割顶）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 2e6+9;
int head[N],numE;
int dfn[N],low[N],bridge[N];
int num,root,ans;
bool cut[N];
struct Edge
{
    int next,to;
}e[N];
void add(int a,int b)
{
    e[numE] = {head[a],b};
    head[a] = numE++;
}
void tarjan(int x)
{
    dfn[x] = low[x] = ++num;
    int flag = 0;
    for(int i=head[x]; ~i; i=e[i].next)
    {
        int y = e[i].to;
        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]);
    }
}
void solve()
{
    memset(head,-1,sizeof head);
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a == b) continue;
        // 这里不continue,是否可以？ 应该是可以的！
        add(a,b);
        add(b,a);
    }
    for(int i=1; i<=n; i++)
    {
        if(!dfn[i]) root = i,tarjan(i);
    }
    for(int i=1; i<=n; i++) if(cut[i]) ans++; //必须最后统计才可以！
    cout<<ans<<"\n";
    for(int i=1; i<=n; i++)
    {
        if(cut[i]) printf("%d ",i);
    }
}
int main()
{
    solve();
    return 0;
}

求割点：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 2e5+9;
int head[N],numE;
int dfn[N],low[N],bridge[N];
int num,root;
bool cut[N];
struct Edge 
{
    int next,to;
}e[N];
void add(int a,int b)
{
    e[numE].next = head[a];
    e[numE].to = b;
    head[a] = numE++;
}
void tarjan(int x)
{
    dfn[x] = low[x] = ++num;
    int flag = 0;
    for(int i=head[x]; ~i; i=e[i].next) 
    {
        int y = e[i].to;
        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]);
    }
}
void solve()
{
    memset(head,-1,sizeof head);
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=m; i++) 
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a == b) continue;
        // 这里不continue,是否可以？
        add(a,b);
        add(b,a);
    }
    for(int i=1; i<=n; i++) 
    {
        if(!dfn[i]) root = i,tarjan(i);
    }
    for(int i=1; i<=n; i++) 
    {
        if(cut[i]) printf("%d ",i);
    }
    puts("\nare cut_vertexes");
}
int main()   
{
    solve();
    return 0;
}

求桥：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 2e5+9;
int head[N],numE;
int dfn[N],low[N],bridge[N];
int num;
struct Edge 
{
    int next,to;
}e[N];
void add(int a,int b)
{
    e[numE].next = head[a];
    e[numE].to = b;
    head[a] = numE++;
}
void tarjan(int x,int in_edge)
{
    dfn[x] = low[x] = ++num;
    for(int i=head[x]; ~i; i=e[i].next) 
    {
        int y = e[i].to;
        if(!dfn[y]) 
        {
            tarjan(y,i);
            low[x] = min(low[x],low[y]);
            if(low[y] > dfn[x]) 
                bridge[i] = bridge[i ^ 1] = 1;
        }
        else if(i != (in_edge ^ 1)) 
            low[x] = min(low[x],dfn[y]);
    }
}
void solve()
{
    memset(head,-1,sizeof head);
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=m; i++) 
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    for(int i=1; i<=n; i++) 
    {
        if(!dfn[i]) tarjan(i,-1);
    }
  //只需要枚举一条边，另一条边为i ^ 1;
    for(int i=0; i<numE; i+=2) 
    {
        if(bridge[i]) printf("%d %d\n",e[i ^ 1].to,e[i].to);
    }
    //for(int i=0; i<numE; i++)
    //{
    //    if(bridge[i]) printf("%d %d\n",e[i ^ 1].to,e[i].to);
    //}
}
int main()   
{
    int t;
    //cin >> t;
    t = 1;
    while(t--) solve();
    return 0;
}