关于点双连通分量

学术版

sgl654321 @ 2024-11-29 10:36:35

给定一个图。如何求出所有点双联通分量，并且输出这些点双连通分量内的所有点和边的编号？

input
5 6
1 2
1 3
2 3
3 4
3 5
4 5
output
2
Node:
1 2 3
3 4 5
Edge:
1 2 3
4 5 6

by qazsedcrfvgyhnujijn @ 2024-11-29 10:38:16

考虑在构建圆方树的时候用 vector 之类的存一下？

by Harumaki_Gohan @ 2024-11-29 10:39:25

tarjan，染色，然后枚举每个点每条边不就行了

by sgl654321 @ 2024-11-29 10:40:39

@Joker_Fish可是一个点可以在多个点双中啊？

by Aria_Math @ 2024-11-29 10:49:23

建圆方树，然后一条边 (u, v) 在树上一定有 dis(u, v) = 2，随便讨论以下就能得到中间那个点的编号了（

by Joker_Fish @ 2024-11-29 10:51:49

@sgl654321我唐了

by sgl654321 @ 2024-11-29 10:52:59

@Aria_Math 这个当然可以了。但是有没有更简单的办法。不用建圆方树可以吗？

by Aria_Math @ 2024-11-29 11:00:05

@sgl654321 好像 Tarjan 的时候可以再开一个栈记录访问了那些边，然后弹栈直到把 (u, v) 弹出去就可以了

|