首页 > 编程语言 >Tarjan 算法及连通性问题

Tarjan 算法及连通性问题

时间:2024-07-29 19:18:24浏览次数:15  
标签:Tarjan 连通性 tarjan 连通 割点 算法 dfn low

无向图的连通性

dfs 树

dfs 树上存在树边和返祖边,不存在横叉边。

割点

若一点 \(u\) 是割点,那么必定存在一个儿子,删去 \(u\) 后和他的父亲不连通。如果不存在,和 \(u\) 相连的所有点依然联通,那么连通性不变,不是割点。

若是根节点,若有至少 \(2\) 个儿子那么就是割点。

判断一个点不经过父亲回到它的祖先,分别记录 \(dfn,low\),分别表示 \(dfs\) 序,和不经过父亲走到的点的最小 \(dfn\) 序。

对于一个点 \(u\),若存在它的一个儿子 \(v\) 满足 \(low_v \le dfn_v\),那么 \(u\) 点就是割点。

void tarjan(int u){
	dfn[u]=low[u]=++cnt;
	
	for(auto v:to[u]){
		if(dfn[v]!=0)low[u]=std::min(low[u],dfn[v]);
		else {
			tarjan(v);
			low[u]=std::min(low[u],low[v]);
		}
	}
}

点双连通分量

点双就是割点分割出的连通块,并上相邻的割点。

可以发现一个点可能存在于多个点双中,但每个点只会出现在一个点双中。

开一个栈,tarjan 访问时把边入栈,如果找到边 \((u,v)\),\(low_v\le dfn_u\),则把栈里的边一一弹出直到 \(u\),构成点双。

也可以存点,但没法对每个点染色。

割边

割边不是返祖边。对于一条树边,如果是割边,那么删除后,上下不连通。

对于一个点,若 \(dfn_u=low_u\),那么它和其父亲间的边就是割边。

边双连通分量

开栈,tarjan 递归将点入栈,若存在点 \(u\) 使得 \(low_u\le dfn_u\),则弹出栈中的边直至点 \(u\),构成边双。

可以对点染色,缩完为一棵树。

Problem 1

\(n\) 点 \(m\) 边的无向图,求至少添加多少边使得任意两点间有两条边不相交的路径。\(n,m\le 10^6\)。

转换成边双(无割边)。

先缩边双,成一棵树,只要计算叶子节点的个数,答案就是 \(\lceil \frac{x}{2}\rceil\)。

P8867 NOIP2022 建造军营

\(n\) 座城市,\(m\) 条双向边连接,联通。

选择至少一座城市建造军营,还可以选择若干条边看守,同时在没有看守的路上会任意断一条边。

求有多少种方案满足不会有两个军营不连通。

HNOI2012 矿场搭建

POJ 2942

有向图的连通性

强连通分量

强连通分量里的点可以相互到达(有向图)。

同样 tarjan 遍历,若出现返祖边,那么就有了一环,环上的点都在一个强连通分量中,判断条件为 \(dfn_u=low_u\)。

ZJOI2007 最大半联通子图

JSOI2010 连通树

APIO2009 抢掠计划

圆方树

标签:Tarjan,连通性,tarjan,连通,割点,算法,dfn,low
From: https://www.cnblogs.com/CheZiHe929/p/18330847

相关文章

  • 2024“钉耙编程”中国大学生算法设计超级联赛(4)
    Preface最唐氏的一集,有人写03一直过不去红温了然后白兰了一整场,怎么回事呢最后很可惜06因为多维数组调用时顺序出了点问题,导致cache爆了然后常数太大TLE了,但凡时间延长1min都改完过了由于今天过的题少就只写过了的六个题,剩下时间还要写昨晚CF的博客最优K子段......
  • 华为OD笔试机试 - 园区参观路径 (Java 2024年C卷D卷真题算法)
    华为OD机试(C卷+D卷)2024真题目录(Java&c++&python)题目描述园区某部门举办了FamilyDay,邀请员工及其家属参加;将公司园区视为一个矩形,起始园区设置在左上角,终点园区设置在右下角;家属参观园区时,只能向右和向下园区前进,求从起始园区到终点园区会有多少条不同的参观路径......
  • 华为OD笔试机试真题算法 - 密码解密 (Java 2024年C卷D卷)
    华为OD机试(C卷+D卷)2024真题目录(Java&c++&python)题目描述给定一段“密文”字符串s,其中字符都是经过“密码本”映射的,现需要将“密文”解密并输出。映射的规则(‘a’~‘i’)分别用(‘1’~‘9’)表示;(‘j’~‘z’)分别用(“10*”~“26*”)表示。约束:映射始终唯一。......
  • 「代码随想录算法训练营」第二十三天 | 贪心算法 part1
    455.分发饼干题目链接:https://leetcode.cn/problems/assign-cookies/题目难度:简单文章讲解:https://programmercarl.com/0455.分发饼干.html视频讲解:https://www.bilibili.com/video/BV1MM411b7cq题目状态:初次有贪心算法的总体概念,有点懵思路:先将饼干尺寸大的满足胃口大......
  • C语言基础算法
    C语言基础算法目录C语言基础算法1、阶乘递归实现循环实现2、排序冒泡排序选择排序3、斐波那契数列4、ASCII码的使用1、阶乘递归实现#include<stdio.h>//递归函数计算阶乘intfactorial(intn){if(n==0||n==1)return1;elsereturnn......
  • 《关于登甲智能建筑图像生成大模型算法的分析报告》
    一、算法全周期行为分析(一)算法安全                    信息内容安全:在生成图片的过程中,需要确保所生成的图片内容不包含违法、有害、侵权或违背社会道德的元素。例如,不能生成具有暴力、色情、歧视等不良内容的图片。信息源安全:对......
  • 问题 E: 深入浅出学算法060-友好城市
    题目描述有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市,但是由于河上雾太大,政府决定避免任意两条航道交叉,以避......
  • 【数据结构】排序算法
    目录排序冒泡排序选择排序直接插入排序希尔排序堆排序归并排序快速排序排序排序的概念:假设含有n个记录的序列为{R1,R2,R3,···,Rn},其相应的关键字分别为{K1,K2,K3,···Kn},需确定1,2,3,···,n的一种排列P1,P2,···,Pn,使其相应的关键字满足Kp1<=Kp2<=K......
  • 山东大学数据结构与算法实验13最小生成树(Prim算法/Kruskal算法)
    A : Prim算法题目描述使用prim算法实现最小生成树输入输出格式输入第一行两个整数n,e。n(1≤n≤200000)代表图中点的个数,e(0≤m≤500000)代表边的个数。接下来e行,每行代表一条边:ijw 表示顶点i和顶点j之间有一条权重为w的边输出最小生成树所有边的......
  • 烧录算法制作
    前言在使用Keil的时候,我们一般会通过一个下载器与目标芯片连接,这样就可以实现的代码下载或调试。那么下载器是如何将我们的应用程序烧写在我们芯片内部Flash当中的呢,是否可以同样的方式烧录在外部Flash上呢?这是此片文章所要说明的。MDK下载算法原理通过MDK创建一批与地址信息无......