Tarjan求割边，Tarjan割边判定

#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], n, m, tot, num;
bool bridge[Size * 2];

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; //注意++ num 不是 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(dfn[x] < low[y])
                bridge[i] = bridge[i ^ 1] = true;
        }else if(i != (in_edge ^ 1))  // 注意加括号
            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;
        add(x, y), add(y, x);
    }
    for(int i = 1; i <= n; ++ i)
        if(!dfn[i]) tarjan(i, 0);
    for(int i = 2; i < tot; ++ i)
        if(bridge[i])
            cout << ver[i ^ 1] << " " << ver[i] << endl;

    return 0;
}

/**
input:
9 11
1 2
2 3
3 4
4 5
1 6
6 7
6 8
8 9
6 9
2 5
1 5
output:
1 6
6 1
6 7
7 6
*/

Tarjan求割点

#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];
int n, m, tot = 1, num, root;
bool cut[Size];

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(dfn[x] <= low[y]){
                flag ++;
                if(x != root || flag > 1) cut[x] = true;
            }
        }else low[x] = min(low[x], dfn[y]);
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1, x, y; i <= m; ++ i){
        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]) cout << i << " ";
    return 0;
}