割边(Tarjan)

题意概述

一个图，个点，条边，求这个图的割边

思路

1. : 点是第几个访问的
2. : 从点出发经过任意条树边，最多一条返祖边，最多一条横插边能回到值最小的那个点
3. 对于，如果, 那么就是一条割边
4. 这里有一个需要和求割点不一样的地方-----返祖边返到了自己的爸爸会发生什么？ 如果这个时候继续更新，那么上面那个式子永远不会成立，那么就没有割边了
5. 用一个pre数组记录每个点在书中的前驱节点

代码

#include <bits/stdc++.h>
const int maxn = 200;
std::vector<int> mat[maxn];
int n = 0, m = 0, u = 0, v = 0;
int low[maxn], dfn[maxn];
int cnt = 0;
int pre[maxn]; // 每个点的前继节点
struct Road
{
    int s;
    int t;
};
bool cmp(Road a, Road b)
{
    if (a.s != b.s)
    {
        return a.s < b.s;
    }
    else
    {
        return a.t < b.t;
    }
}
std::vector<Road> ans;
void tarjan(int x)
{
    low[x] = dfn[x] = ++cnt;
    std::cout << "这一轮开始前low[" << x << "] = " << low[x] << '\n';  
    for (int i = 0; i < mat[x].size(); i++)
    {
        int y = mat[x][i];
        if (dfn[y] == 0) // 如果是树边
        {
            pre[y] = x;
            tarjan(y);
            low[x] = std::min(low[x], low[y]);
            if (low[y] > dfn[x])
            {
                Road tmp;
                tmp.s = x, tmp.t = y;
                ans.push_back(tmp);
            }
        }
        if(dfn[y] && y != pre[x]) // 如果是返祖边
        {
            low[x] = std::min(low[x], dfn[y]);
        }
    }
    std::cout << "这一轮结束后low[" << x << "] = " << low[x] << '\n';
}


int main()
{
    std::cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        std::cin >> u >> v;
        mat[u].push_back(v);
        mat[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
    {
        if (dfn[i] == 0)
        {
            tarjan(i);
        }
    }
    return 0;
}