(模板)割边

割边(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;
}
全部评论

相关推荐

点赞 评论 收藏
分享
每晚夜里独自颤抖:要求太多的没必要理
点赞 评论 收藏
分享
zzzzhz:兄弟你先猛猛投简历至少三百家,能约到面试就去面。最近可以速成智能小车,智慧家居烂大街的项目,不需要自己写,只需要把里面的代码讲解看明白就行。把其中涉及到的八股文都拿出来单独背一下,我去年找工作就一个智能小车智慧家居找了10k差不多。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务