双连通分量例题

[CEOI2017] One-Way Streets题意给定一个无向连通图以及若干对点 (x, y)要求给每条边定向使得 x 能到达 y求哪些边的方向是唯一确定的并输出其方向。环上的边方向不唯一如果一条无向边 (u, v) 位于任何一个环中那么它在环上的方向是可以灵活调整的。无论它指向 u - v 还是 v - u环都能保证环上任意两点间有路径。因此这类边永远无法被强迫指向某一个特定方向答案是 ‘B’Both。所以我们可以把所有不在环上的边也就是桥找出来只有这些边才可能有唯一方向。既然环上的边都是 “B”我们可以把它们全部忽略因为它们不贡献任何答案。删除所有桥剩下的每个连通块都是一个边双连通分量内部任意两点间至少有两条边不相交的路径。将每个边双连通分量缩成一个点。连接这些点的边正好就是原图中的所有桥。缩点后整个图会变成一棵树或森林。至此问题被完全转化到了树上。树上的每条边都对应原图的一座桥是我们需要判断方向的候选对象。现在我们有一个限制条件 (x, y)意思是原图中点 x 必须能到达点 y。在缩点后的树中x 和 y 所在的节点之间有且仅有一条唯一路径。为了让 x 能到达 y这条路径上的所有边都必须指向从 x 到 y 的方向。反向的边以及路径之外的边都不受这个条件影响。当有多个限制条件时每条边的方向将由覆盖它的所有路径共同决定。如果一条边被某个路径要求指向 A - B又被另一个路径要求指向 B - A那么就会产生冲突这条边的方向无法确定答案是 ‘B’。如果所有覆盖它的路径都要求指向同一个方向那么这个方向就是唯一确定的。如果没有任何路径经过这条边它的方向也不确定答案是 ‘B’。计算答案我们需要高效地处理多条路径对树边的影响。树上差分正是解决这类问题的利器。我们可以给每个树节点一个权值 diff用它来统计经过该节点与其父节点之间这条边的路径信息标记路径对于每个限制 (x, y)我们做 diff[x] 1diff[y] - 1或在求LCA后做更标准的边差分但核心思想一致。这样做可以记录下路径的起点和终点。自底向上累加通过一次DFS计算每个节点的子树 diff 值之和。这个累加和 sum[v] 代表了所有经过节点 v 与它父节点之间这条边的路径的净数量。解读差分值如果 sum[v] 0说明从 v 子树方向到父节点方向的路径更多因此边 (v, parent[v]) 应指向父节点方向。如果 sum[v] 0说明从父节点方向到 v 子树方向的路径更多边应指向子节点 v 方向。如果 sum[v] 0说明没有路径覆盖这条边或有正有负恰好抵消但后者意味着存在冲突因此方向不唯一。[SCCPC 2026]环基基环树题意你有一棵基环树n 个点n 条边恰好一个环。现在对这棵树进行变异操作每个点 u 变成一个长度至少为 3 的简单环 C_u原图中的每条边 (u, v) 变成连接环 C_u 和环 C_v 之间的一条边变异后得到一个新图。现在给你这个变异后的图请你还原出原来的基环树。输出格式输出还原后的基环树的点数和所有边。变换后的图中有三类结构每个原图点扩展出来的简单环原图基环上的边对应扩展环之间的非桥连接边原图基环外的树枝边对应扩展环之间的桥。因此先找出所有桥并删去。删去桥后每个扩展环内部的边仍然存在原图基环上的连接边仍然存在原图基环外的树枝连接边被删去。删去桥后的度数性质考虑删去桥后的图。对于某个扩展环Cx如果环上的一个点没有承担原图基环上的连接边那么它只和环上的左右两个相邻点相连度数为2如果环上的一个点承担了原图基环上的连接边那么它除了两个环内邻点外还会连接到别的扩展环度数至少为3。由于原图是基环树每个原图点在基环上至多有两条非桥连接边。又因为cx ≥3每个扩展环中一定存在度数为2的点缩回一个扩展环在删去桥后的图中如果一个点的度数为2那么它的两条边一定都是所在扩展环的环内边。因此这个点和它的两个邻点一定来自原图中的同一个点应当被缩成同一个点。不断利用这个性质同一个扩展环上的点会被全部合并。同时不同扩展环之间的连接边不会导致错误合并因为连接边的端点在删去桥后的图中度数至少为3不会作为度数为2的点去合并两侧。按上述规则缩点后每个缩点恰好对应原图中的一个点还原原图边完成缩点后重新考虑变换后图中的每条边(u,v)。设u 所在缩点为Uv 所在缩点为V。若U V说明这条边是某个扩展环内部的边不属于原图若U ̸ V说明这条边连接了两个扩展环对应原图中的一条边。因此输出所有跨缩点的边就得到还原后的基环树。时间复杂度和空间复杂度均为O(nm)。