当前位置: 首页 > news >正文

P3388 【模板】割点(割顶) tarjan

解题思路

割点(割顶):在一个无向图中,如果删除某个顶点以及与之相连的所有边后,图的连通分量数量增加,则该顶点称为割点。

Tarjan算法求割点的核心思想:

  1. 使用深度优先搜索遍历图

  2. 维护两个数组:

    • dfn[i]:顶点i的深度优先搜索遍历序号(时间戳)

    • low[i]:顶点i能够回溯到的最早的祖先节点的dfn值

  3. 割点的判断条件:

    • 对于根节点:如果有2个或以上的子树,则它是割点

    • 对于非根节点:如果存在子节点y满足low[y] >= dfn[x],则x是割点

      #include<bits/stdc++.h>
      #define ll long long
      using namespace std;
      const int N = 2e5 + 10,inf = 0x3f3f3f3f;
      vector<int> g[N];  // 邻接表存储图
      int dfn[N],low[N],f[N],id;  // dfn:时间戳,low:能回溯到的最小dfn,f:父节点,id:时间戳计数器
      int vis[N];  // 标记节点是否为割点
      int ans;     // 割点数量
      int n,m;     // 顶点数,边数void tarjan(int x,int fa)  // Tarjan算法,x:当前节点,fa:父节点
      {dfn[x] = low[x] = ++id;  // 初始化当前节点的dfn和low值f[x] = fa;               // 记录父节点int cnt = 0;             // 记录当前节点的子节点数量(用于判断根节点是否为割点)for(int i = 0; i < g[x].size(); i++){int y = g[x][i];  // 邻接节点yif(dfn[y] == 0){  // 如果y未被访问过(树边)cnt++;        // 子节点计数+1tarjan(y,x);  // 递归遍历子节点
                  low[x] = min(low[x],low[y]);  // 更新当前节点的low值// 判断割点条件:if(f[x] == 0){  // 如果x是根节点if(cnt >= 2) vis[x] = 1;  // 根节点有>=2个子树则是割点
                  }else if(low[y] >= dfn[x]) vis[x] = 1;  // 非根节点:存在子节点y满足low[y]>=dfn[x]
              }else if(y != f[x]) low[x] = min(low[x],dfn[y]);  // 回边,更新low值
          }
      }int main()
      {cin >> n >> m;// 读入图数据,构建无向图for(int i = 1; i <= m; i++){int x,y; cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}// 遍历所有连通分量(因为图可能不连通)for(int i = 1; i <= n; i++){if(dfn[i] == 0)  // 如果节点i未被访问过tarjan(i,0); // 从i开始Tarjan算法,父节点设为0(表示根节点)
          }// 统计割点数量for(int i = 1; i <= n; i++)if(vis[i]) ans++;// 输出结果cout << ans << endl;for(int i = 1; i <= n; i++)if(vis[i])cout << i << " ";return 0;
      }

       

http://www.hskmm.com/?act=detail&tid=27574

相关文章:

  • new day
  • 10.9每日总结
  • vLLM 吞吐量优化实战:10个KV-Cache调优方法让tokens/sec翻倍
  • Linux之周期性定时任务实践
  • MyBatis-Plus 的 QueryWrapper 应用以及在内存中处理JSON数组字符串匹配
  • P9461 「EZEC-14」众数 II
  • 提升
  • 详细介绍:win11 安装 WSL2 Ubuntu 并支持远程 SSH 登录
  • Ai元人文:论智能的“全息定帧”与“渐进式显影”机制
  • 24 LCA模拟赛2T4 colorful 题解
  • 23 LCA模拟赛2T2 异或排列 题解
  • Bugkuctf的哥哥的秘密
  • 国庆做题记录(基础算法)
  • fp16训练神经网络时出现nan问题
  • 第十篇
  • 504 品酒大会!!!!!!
  • 整体理解pai0-具身智能-01 - jack
  • 【数据结构】可撤销并查集 - Slayer
  • 皮卡鱼源码导读
  • 高斯消元学习笔记
  • newDay07
  • 10月9日
  • 从开放重定向到XSS:漏洞升级实战
  • 余弦日记
  • 【题解】P11459 [USACO24DEC] Its Mooin Time P
  • 创建一个springboot项目,mybatis连接嵌入式数据库H2,实现增删改查功能
  • 基于众包的产品质量比较与推荐算法研究
  • 10/9
  • 2025.10.9
  • 线程池总结