算法设计与分析的作业，打个卡，用 dfs 寻找割点和桥

题目描述

给出一个无向连通图，找到所有的割点和桥

输入

第一行：点的个数，如果点个数是n，他们的编号为0 ~ n-1

余下的行：每行代表一条边，如“0 2”代表顶点0和顶点2有一条边 (一条边只出现一次，如出现“0 2”则不会出现“2 0”)

输出

所有的割点和所有的桥，先输出割点再输出桥

割点按编号升序排列，桥按边的升序排列，如“0 2”小于“0 3”，“1 5”小于“2 3”（边的输出和排列总是把小顶点放前面，所以输出总是“0 2”而非“2 0”）

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 2e4 + 10, M = 2e5 + 10;

int h[N], e[M], ne[M], idx, globalTime;

enum COLOR {
    WHITE, GRAY, BLACK
};

COLOR color[N];

int discoverTime[N], back[N],cnt[N];
bool isRoot[N];
vector<int> ap;
vector<pair<int,int>> bg;

void dfs_ap(int v, int p){
    color[v] = GRAY;
    globalTime ++;
    discoverTime[v] = globalTime;
    back[v] = discoverTime[v];
    for(int i = h[v]; i != -1; i = ne[i]){
        int j = e[i];
        if(color[j] == WHITE){
            cnt[v] ++;
            dfs_ap(j, v);
            if(back[j] >= discoverTime[v] && !isRoot[v]){
                ap.push_back(v);
            }
            back[v] = min(back[v], back[j]);
        }else{
            if(color[j] == GRAY && j != p){
                back[v] = min(back[v], discoverTime[j]);
            }
        }
    }
}

void dfs_bg(int u, int p){
    color[u] = GRAY;
    globalTime ++;
    discoverTime[u] = globalTime;
    back[u] = discoverTime[u];
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(color[j] == WHITE){
            dfs_bg(j, u);
            back[u] = min(back[u], back[j]);
            if(back[j] > discoverTime[u]){
                if(j < u)bg.push_back({j, u});
                else bg.push_back({u, j});
            }
        }else{
            if(color[j] == GRAY && j != p){
                back[u] = min(back[u], discoverTime[j]);
            }
        }
    }
}

void addArc(int x, int y){
    e[idx] = y;
    ne[idx] = h[x];
    h[x] = idx ++;
}

int main(){
    int n;
    cin >> n;
    int x, y;
    memset(h, -1, sizeof h);

    while(scanf("%d%d", &x, &y) != EOF){
        addArc(x, y);
        addArc(y, x);
    }

    for(int i = 0; i < n; i ++){
        if(color[i] == WHITE){
            isRoot[i] = true;
            dfs_ap(i, -1);
            if(cnt[i] > 1)ap.push_back(i);
        }
    }
    memset(color, 0, sizeof color);
    memset(back, 0, sizeof back);
    memset(discoverTime, 0, sizeof discoverTime);
    globalTime = 0;

    for(int i = 0; i < n; i ++){
        if(color[i] == WHITE){
            dfs_bg(i, -1);
        }
    }


    sort(ap.begin(), ap.end());
    sort(bg.begin(), bg.end());

    int len = ap.size();
    for(int i = 0; i < len; i ++)cout << ap[i] << endl;
    len = bg.size();
    for(int i = 0; i < len; i ++)cout << bg[i].first << " " << bg[i].second << endl;
    return 0;
}