当前位置:网站首页>无向图的桥
无向图的桥
2022-07-02 09:46:00 【chengqiuming】
一 点睛
时间戳:dfn[u] 表示节点 u 深度优先遍历的序号。
追溯点:low[u]表示节点u或u的子孙能通过非父子追溯到dfn最小节点的序号,即回到最早的过去。
二 举例
初始时,dfn[u]=low[u],如果该节点的邻节点未被访问,则一直进行深度优先遍历,1-2-3-5-6-4,此时 4 的邻接点 1 已被访问,且 1 不是 4 的父节点,4 的父节点是6(深度优先搜索树上的父节点)。
节点 4 能回到最早的节点是节点1(dfn=1),因此low[4]=min(low[4],dfn[1])=1,返回时,更新low[6]=min(low[6],low[4])=1。更新路径上所有祖先节点的 low 值,因为子孙能回到的追溯点,其祖先也能回到。
三 无向图的桥
桥判定法则:无向边 x-y 是桥,当且仅当搜索树上存在一个节点 y,满足 low[y] > dfn[x]。
也就是说,如果孩子的 low 值比自己大,则从该节点到这个孩子的边为桥。在上图中,边5-7中,5的子节点为7,满足 low[7]>dfn[5],因此 5-7 为桥。
四 代码
package graph.tarjanbridge;
import java.util.Arrays;
import java.util.Scanner;
public class TarjanBridge {
static int SIZE = 100010;
static int head[] = new int[SIZE], to[] = new int[SIZE << 1], next[] = new int[SIZE << 1];
static int cnt = 0;
static void addEdge(int x, int y) {
to[cnt] = y;
next[cnt] = head[x];
head[x] = cnt++;
to[cnt] = x;
next[cnt] = head[y];
head[y] = cnt++;
}
static int dfn[] = new int[SIZE], low[] = new int[SIZE];
static int index;
static boolean bridge[] = new boolean[SIZE << 1];
static void tarjan(int x, int edge) {
dfn[x] = low[x] = ++index;
for (int i = head[x]; i >= 0; i = next[i]) {
int y = to[i];
if (dfn[y] == 0) {
tarjan(y, i);
low[x] = Math.min(low[x], low[y]);
if (dfn[x] < low[y])
bridge[i] = bridge[i ^ 1] = true;
} else if (i != (edge ^ 1))
low[x] = Math.min(low[x], dfn[y]);
}
}
static void init() {
Arrays.fill(head, -1);
cnt = 0;
}
static int n, m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
init();
for (int i = 0; i < m; i++)
addEdge(sc.nextInt(), sc.nextInt());
for (int i = 1; i <= n; i++)
if (dfn[i] == 0)
tarjan(i, -1);
for (int i = 1; i < cnt; i += 2)
if (bridge[i])
System.out.println(to[i ^ 1] + " " + to[i]);
}
}
五 测试
边栏推荐
- (6) Web security | penetration test | network security encryption and decryption ciphertext related features, with super encryption and decryption software
- NTMFS4C05NT1G N-CH 30V 11.9A MOS管,PDF
- 8A Synchronous Step-Down regulator tps568230rjer_ Specification information
- Hash table acwing 840 Simulated hash table
- Js8day (rolling event (scroll family), offset family, client family, carousel map case (to be done))
- Wechat official account payment prompt MCH_ ID parameter format error
- Js3day (array operation, JS bubble sort, function, debug window, scope and scope chain, anonymous function, object, Math object)
- Fundamentals of face recognition (facenet)
- Rust语言文档精简版(上)——cargo、输出、基础语法、数据类型、所有权、结构体、枚举和模式匹配
- Apply lnk306gn-tl converter, non isolated power supply
猜你喜欢
Unity SKFramework框架(十六)、Package Manager 开发工具包管理器
Linear DP acwing 898 Number triangle
Everyone wants to eat a broken buffet. It's almost cold
[error record] cannot open "XXX" because Apple cannot check whether it contains malware
模数转换器(ADC) ADE7913ARIZ 专为三相电能计量应用而设计
Ali on three sides, it's really difficult to successfully get the offer rated P7
PR usage skills, how to use PR to watermark?
[opencv learning] [contour detection]
Counter attack of flour dregs: MySQL 66 questions, 20000 words + 50 pictures in detail! A little six
Ltc3307ahv meets EMI standard, step-down converter qca7005-al33 phy
随机推荐
Rust language document Lite (Part 1) - cargo, output, basic syntax, data type, ownership, structure, enumeration and pattern matching
Js3day (array operation, JS bubble sort, function, debug window, scope and scope chain, anonymous function, object, Math object)
JS generates 4-digit verification code
West digital decided to raise the price of flash memory products immediately after the factory was polluted by materials
Heap acwing 838 Heap sort
Direct control PTZ PTZ PTZ PTZ camera debugging (c)
Jerry's watch gets the default ringtone selection list [article]
Traverse entrylist method correctly
MySQL: Invalid GIS data provided to function st_ geometryfromtext
基于STM32的OLED 屏幕驱动
Interview questions for software testing - a collection of interview questions for large factories in 2022
Js1day (input / output syntax, data type, data type conversion, VaR and let differences)
百款拿来就能用的网页特效,不来看看吗?
Visual studio efficient and practical extension tools and plug-ins
8 examples of using date commands
C#运算符
Word efficiency guide - word's own template
Window10 upgrade encountered a big hole error code: 0xc000000e perfect solution
Std:: vector batch import fast de duplication method
Unity SKFramework框架(十三)、Question 问题模块