結果
| 問題 |
No.1254 補強への架け橋
|
| コンテスト | |
| ユーザー |
 草苺奶昔
|
| 提出日時 | 2024-05-01 18:00:41 |
| 言語 | Go (1.23.4) |
| 結果 |
AC
|
| 実行時間 | 142 ms / 2,000 ms |
| コード長 | 16,250 bytes |
| コンパイル時間 | 14,295 ms |
| コンパイル使用メモリ | 220,188 KB |
| 実行使用メモリ | 15,616 KB |
| 最終ジャッジ日時 | 2024-11-21 23:37:31 |
| 合計ジャッジ時間 | 27,745 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 123 |
ソースコード
// https://maspypy.github.io/library/graph/unicyclic.hpp
// !Namori Graph 无向图基环树
// !一个有 n 个顶点和 n 条边的“连通”无向图。图中只有一个环。
// 这个图被称为“Namori图”，这是根据一位漫画家的名字而命名的，
// 但在学术界中，正确的称呼是“单环图(Unicyclic)”或“伪森林(Pseudoforest)”。
// 例如：下图是一个无向基环树，其中的边权都是1。
//
// 0
// |
// 1
// / \
// 2 3 - 4 - 5
// \ /
// 6
//
// root: 3
// outEdge: 3-6
// to: [1 3 1 6 3 4 2]
// cycle: [6 2 1 3] (bottom到root的路径)
// directedGraph:
//
// 3(root)
// / \
// 1 4
// / \ \
// 0 2 5
// \
// 6(bottom)
//
// !性质1：点u在所在子树的根节点(在环上)为lca(u, bottom).
//
// !这种维护方法的优势是支持动态修改点权或者边权
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
yuki1254()
// abc266f()
// namoriCut()
}
// https://yukicoder.me/problems/no/1254
// 找基环树中的环上的边.
func yuki1254() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n int32
fmt.Fscan(in, &n)
edges := make([]edge, n)
for i := int32(0); i < n; i++ {
var u, v int32
fmt.Fscan(in, &u, &v)
u--
v--
edges[i] = edge{u: u, v: v, w: 1}
}
namori := NewNamoriGraph(n, edges)
res := []int32{}
for i, e := range edges {
if namori.InCycle[e.u] && namori.InCycle[e.v] {
res = append(res, int32(i+1))
}
}
fmt.Fprintln(out, len(res))
for _, v := range res {
fmt.Fprint(out, v, " ")
}
}
// https://atcoder.jp/contests/abc266/tasks/abc266_f
// 每次查询基环树中两个点是否由唯一的路径相连.
// 等价于：所在子树的根节点是否相同.
func abc266f() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n int32
fmt.Fscan(in, &n)
edges := make([]edge, n)
for i := int32(0); i < n; i++ {
var u, v int32
fmt.Fscan(in, &u, &v)
u--
v--
edges[i] = edge{u, v, 1}
}
var q int32
fmt.Fscan(in, &q)
queries := make([][2]int32, q)
for i := int32(0); i < q; i++ {
var u, v int32
fmt.Fscan(in, &u, &v)
u--
v--
queries[i] = [2]int32{u, v}
}
namori := NewNamoriGraph(n, edges)
_, tree := namori.BuildTree()
root := namori.Root
bottom := namori.To[root]
for _, q := range queries {
u, v := q[0], q[1]
lca1, lca2 := tree.LCA(u, bottom), tree.LCA(v, bottom)
if lca1 == lca2 {
fmt.Fprintln(out, "Yes")
} else {
fmt.Fprintln(out, "No")
}
}
}
func namoriCut() {
// https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2891
// 给定一个基环树 q个询问(x,y)
// 求使得x和y不连通最少需要切掉多少条边
// 如果两个点都在环上,则答案为2
// 否则答案为1(两点之间只有唯一的一条路径)
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n int32
fmt.Fscan(in, &n)
edges := make([]edge, n)
for i := int32(0); i < n; i++ {
var a, b int32
fmt.Fscan(in, &a, &b)
a, b = a-1, b-1
edges[i] = edge{a, b, 1}
}
G := NewNamoriGraph(n, edges)
_, tree := G.BuildTree()
root := G.Root
bottom := G.To[root]
var q int32
fmt.Fscan(in, &q)
for i := int32(0); i < q; i++ {
var x, y int32
fmt.Fscan(in, &x, &y)
x, y = x-1, y-1
lca1, lca2 := tree.LCA(x, bottom), tree.LCA(y, bottom)
if lca1 == lca2 {
fmt.Fprintln(out, 1)
} else {
fmt.Fprintln(out, 2)
}
}
}
func demo() {
edges := []edge{
{0, 1, 1}, {1, 2, 2}, {1, 3, 3}, {2, 6, 6}, {3, 6, 6}, {3, 4, 4}, {4, 5, 5},
}
namori := NewNamoriGraph(7, edges)
fmt.Println(namori.Root)
fmt.Println(namori.OutEdgeId)
fmt.Println(namori.OutCost)
fmt.Println(namori.To)
fmt.Println(namori.Cycle)
directedGraph, tree := namori.BuildTree()
fmt.Println(directedGraph)
fmt.Println(namori.Dist(tree, 0, 5))
}
type edge = struct {
u, v int32
w int
}
type neighbor = struct {
to, eid int32
weight int
}
// !无向基环树.
type NamoriGraph struct {
RawEdges []edge
RawGraph [][]neighbor
N int32
Root int32 // 断开outEdge后有向树的根
OutEdgeId int32 // build后不在树中的边
OutCost int
To []int32 // !向Root方向移动1步后的结点，Root的To为对应outEdge的另一端
Cycle []int32
InCycle []bool
}
func NewNamoriGraph(n int32, edges []edge) *NamoriGraph {
m := int32(len(edges))
if m != n {
panic("invalid namori graph")
}
graph := make([][]neighbor, n)
for eid := int32(0); eid < m; eid++ {
e := &edges[eid]
u, v, w := e.u, e.v, e.w
graph[u] = append(graph[u], neighbor{to: v, weight: w, eid: eid})
graph[v] = append(graph[v], neighbor{to: u, weight: w, eid: eid})
}
uf := newUnionFindArraySimple32(n)
to := make([]int32, n)
for i := range to {
to[i] = -1
}
root := int32(-1)
outEdgeId, outCost := int32(-1), -1
for eid := int32(0); eid < m; eid++ {
e := &edges[eid]
u, v, w := e.u, e.v, e.w
if uf.Union(u, v) {
continue
}
outEdgeId, outCost = eid, w
root = u
to[root] = v
break
}
visited := make([]bool, n)
stack := []int32{root}
for len(stack) > 0 {
pre := stack[len(stack)-1]
stack = stack[:len(stack)-1]
visited[pre] = true
for _, e := range graph[pre] {
next, eid := e.to, e.eid
if visited[next] || eid == outEdgeId {
continue
}
to[next] = pre
stack = append(stack, next)
}
}
cycle := []int32{to[root]}
for cycle[len(cycle)-1] != root {
cycle = append(cycle, to[cycle[len(cycle)-1]])
}
inCycle := make([]bool, n)
for _, v := range cycle {
inCycle[v] = true
}
return &NamoriGraph{
RawEdges: edges,
RawGraph: graph,
N: n,
Root: root,
OutEdgeId: outEdgeId,
OutCost: outCost,
To: to,
Cycle: cycle,
InCycle: inCycle,
}
}
// 断开outEdge, 生成有向树.
func (ng *NamoriGraph) BuildTree() (directedGraph [][]neighbor, tree *Tree) {
directedGraph = make([][]neighbor, ng.N)
for eid := int32(0); eid < ng.N; eid++ {
if eid == ng.OutEdgeId {
continue
}
e := &ng.RawEdges[eid]
u, v, w := e.u, e.v, e.w
if ng.To[u] == v {
u, v = v, u
}
directedGraph[u] = append(directedGraph[u], neighbor{to: v, weight: w, eid: eid})
}
tree = NewTree(directedGraph)
tree.Build(ng.Root)
return
}
// 基环树求距离.
func (ng *NamoriGraph) Dist(tree *Tree, u, v int32) int32 {
bottom := ng.To[ng.Root]
// lca为在环上的点
lca1, lca2 := tree.LCA(u, bottom), tree.LCA(v, bottom)
distOnCyle := abs32(tree.Depth[lca1] - tree.Depth[lca2])
distOnCyle = min32(distOnCyle, int32(len(ng.Cycle))-distOnCyle)
return distOnCyle + tree.Depth[u] + tree.Depth[v] - tree.Depth[lca1] - tree.Depth[lca2]
}
func (ng *NamoriGraph) DistWeighted(tree *Tree, u, v int32) int {
bottom := ng.To[ng.Root]
lca1, lca2 := tree.LCA(u, bottom), tree.LCA(v, bottom)
distOnCycle := abs(tree.DepthWeighted[lca1] - tree.DepthWeighted[lca2])
distOnCycle = min(distOnCycle, tree.DepthWeighted[bottom]+ng.OutCost-distOnCycle)
return distOnCycle + tree.DepthWeighted[u] + tree.DepthWeighted[v] - tree.DepthWeighted[lca1] - tree.DepthWeighted[lca2]
}
type unionFindArraySimple32 struct {
Part int32
n int32
data []int32
}
func newUnionFindArraySimple32(n int32) *unionFindArraySimple32 {
data := make([]int32, n)
for i := int32(0); i < n; i++ {
data[i] = -1
}
return &unionFindArraySimple32{Part: n, n: n, data: data}
}
func (u *unionFindArraySimple32) Union(key1, key2 int32) bool {
root1, root2 := u.Find(key1), u.Find(key2)
if root1 == root2 {
return false
}
if u.data[root1] > u.data[root2] {
root1, root2 = root2, root1
}
u.data[root1] += u.data[root2]
u.data[root2] = int32(root1)
u.Part--
return true
}
func (u *unionFindArraySimple32) Find(key int32) int32 {
if u.data[key] < 0 {
return key
}
u.data[key] = u.Find(u.data[key])
return u.data[key]
}
func (u *unionFindArraySimple32) GetSize(key int32) int32 {
return -u.data[u.Find(key)]
}
type Tree struct {
Tree [][]neighbor // (next, weight)
Depth []int32
DepthWeighted []int
Parent []int32
LID, RID []int32 // 欧拉序[in,out)
IdToNode []int32
top, heavySon []int32
timer int32
}
func NewTree(graph [][]neighbor) *Tree {
n := int32(len(graph))
tree := graph
lid := make([]int32, n)
rid := make([]int32, n)
IdToNode := make([]int32, n)
top := make([]int32, n) // 所处轻/重链的顶点（深度最小），轻链的顶点为自身
depth := make([]int32, n) // 深度
depthWeighted := make([]int, n)
parent := make([]int32, n) // 父结点
heavySon := make([]int32, n) // 重儿子
for i := range parent {
parent[i] = -1
}
return &Tree{
Tree: tree,
Depth: depth,
DepthWeighted: depthWeighted,
Parent: parent,
LID: lid,
RID: rid,
IdToNode: IdToNode,
top: top,
heavySon: heavySon,
}
}
// root:0-based
//
// 当root设为-1时，会从0开始遍历未访问过的连通分量
func (tree *Tree) Build(root int32) {
if root != -1 {
tree.build(root, -1, 0, 0)
tree.markTop(root, root)
} else {
for i := int32(0); i < int32(len(tree.Tree)); i++ {
if tree.Parent[i] == -1 {
tree.build(i, -1, 0, 0)
tree.markTop(i, i)
}
}
}
}
// 返回 root 的欧拉序区间, 左闭右开, 0-indexed.
func (tree *Tree) Id(root int32) (int32, int32) {
return tree.LID[root], tree.RID[root]
}
// 返回返回边 u-v 对应的 欧拉序起点编号, 1 <= eid <= n-1., 0-indexed.
func (tree *Tree) Eid(u, v int32) int32 {
if tree.LID[u] > tree.LID[v] {
return tree.LID[u]
}
return tree.LID[v]
}
func (tree *Tree) LCA(u, v int32) int32 {
for {
if tree.LID[u] > tree.LID[v] {
u, v = v, u
}
if tree.top[u] == tree.top[v] {
return u
}
v = tree.Parent[tree.top[v]]
}
}
func (tree *Tree) RootedLCA(u, v int32, root int32) int32 {
return tree.LCA(u, v) ^ tree.LCA(u, root) ^ tree.LCA(v, root)
}
func (tree *Tree) RootedParent(u int32, root int32) int32 {
return tree.Jump(u, root, 1)
}
func (tree *Tree) Dist(u, v int32, weighted bool) int {
if weighted {
return tree.DepthWeighted[u] + tree.DepthWeighted[v] - 2*tree.DepthWeighted[tree.LCA(u, v)]
}
return int(tree.Depth[u] + tree.Depth[v] - 2*tree.Depth[tree.LCA(u, v)])
}
// k: 0-based
//
// 如果不存在第k个祖先，返回-1
// kthAncestor(root,0) == root
func (tree *Tree) KthAncestor(root, k int32) int32 {
if k > tree.Depth[root] {
return -1
}
for {
u := tree.top[root]
if tree.LID[root]-k >= tree.LID[u] {
return tree.IdToNode[tree.LID[root]-k]
}
k -= tree.LID[root] - tree.LID[u] + 1
root = tree.Parent[u]
}
}
// 从 from 节点跳向 to 节点,跳过 step 个节点(0-indexed)
//
// 返回跳到的节点,如果不存在这样的节点,返回-1
func (tree *Tree) Jump(from, to, step int32) int32 {
if step == 1 {
if from == to {
return -1
}
if tree.IsInSubtree(to, from) {
return tree.KthAncestor(to, tree.Depth[to]-tree.Depth[from]-1)
}
return tree.Parent[from]
}
c := tree.LCA(from, to)
dac := tree.Depth[from] - tree.Depth[c]
dbc := tree.Depth[to] - tree.Depth[c]
if step > dac+dbc {
return -1
}
if step <= dac {
return tree.KthAncestor(from, step)
}
return tree.KthAncestor(to, dac+dbc-step)
}
func (tree *Tree) CollectChild(root int32) []int32 {
res := []int32{}
for _, e := range tree.Tree[root] {
next := e.to
if next != tree.Parent[root] {
res = append(res, next)
}
}
return res
}
// 返回沿着`路径顺序`的 [起点,终点] 的 欧拉序 `左闭右闭` 数组.
//
// !eg:[[2 0] [4 4]] 沿着路径顺序但不一定沿着欧拉序.
func (tree *Tree) GetPathDecomposition(u, v int32, vertex bool) [][2]int32 {
up, down := [][2]int32{}, [][2]int32{}
for {
if tree.top[u] == tree.top[v] {
break
}
if tree.LID[u] < tree.LID[v] {
down = append(down, [2]int32{tree.LID[tree.top[v]], tree.LID[v]})
v = tree.Parent[tree.top[v]]
} else {
up = append(up, [2]int32{tree.LID[u], tree.LID[tree.top[u]]})
u = tree.Parent[tree.top[u]]
}
}
edgeInt := int32(1)
if vertex {
edgeInt = 0
}
if tree.LID[u] < tree.LID[v] {
down = append(down, [2]int32{tree.LID[u] + edgeInt, tree.LID[v]})
} else if tree.LID[v]+edgeInt <= tree.LID[u] {
up = append(up, [2]int32{tree.LID[u], tree.LID[v] + edgeInt})
}
for i := 0; i < len(down)/2; i++ {
down[i], down[len(down)-1-i] = down[len(down)-1-i], down[i]
}
return append(up, down...)
}
// 遍历路径上的 `[起点,终点)` 欧拉序 `左闭右开` 区间.
func (tree *Tree) EnumeratePathDecomposition(u, v int32, vertex bool, f func(start, end int32)) {
for {
if tree.top[u] == tree.top[v] {
break
}
if tree.LID[u] < tree.LID[v] {
a, b := tree.LID[tree.top[v]], tree.LID[v]
if a > b {
a, b = b, a
}
f(a, b+1)
v = tree.Parent[tree.top[v]]
} else {
a, b := tree.LID[u], tree.LID[tree.top[u]]
if a > b {
a, b = b, a
}
f(a, b+1)
u = tree.Parent[tree.top[u]]
}
}
edgeInt := int32(1)
if vertex {
edgeInt = 0
}
if tree.LID[u] < tree.LID[v] {
a, b := tree.LID[u]+edgeInt, tree.LID[v]
if a > b {
a, b = b, a
}
f(a, b+1)
} else if tree.LID[v]+edgeInt <= tree.LID[u] {
a, b := tree.LID[u], tree.LID[v]+edgeInt
if a > b {
a, b = b, a
}
f(a, b+1)
}
}
func (tree *Tree) GetPath(u, v int32) []int32 {
res := []int32{}
composition := tree.GetPathDecomposition(u, v, true)
for _, e := range composition {
a, b := e[0], e[1]
if a <= b {
for i := a; i <= b; i++ {
res = append(res, tree.IdToNode[i])
}
} else {
for i := a; i >= b; i-- {
res = append(res, tree.IdToNode[i])
}
}
}
return res
}
// 以root为根时,结点v的子树大小.
func (tree *Tree) SubSize(v, root int32) int32 {
if root == -1 {
return tree.RID[v] - tree.LID[v]
}
if v == root {
return int32(len(tree.Tree))
}
x := tree.Jump(v, root, 1)
if tree.IsInSubtree(v, x) {
return tree.RID[v] - tree.LID[v]
}
return int32(len(tree.Tree)) - tree.RID[x] + tree.LID[x]
}
// child 是否在 root 的子树中 (child和root不能相等)
func (tree *Tree) IsInSubtree(child, root int32) bool {
return tree.LID[root] <= tree.LID[child] && tree.LID[child] < tree.RID[root]
}
// 寻找以 start 为 top 的重链 ,heavyPath[-1] 即为重链底端节点.
func (tree *Tree) GetHeavyPath(start int32) []int32 {
heavyPath := []int32{start}
cur := start
for tree.heavySon[cur] != -1 {
cur = tree.heavySon[cur]
heavyPath = append(heavyPath, cur)
}
return heavyPath
}
// 结点v的重儿子.如果没有重儿子,返回-1.
func (tree *Tree) GetHeavyChild(v int32) int32 {
k := tree.LID[v] + 1
if k == int32(len(tree.Tree)) {
return -1
}
w := tree.IdToNode[k]
if tree.Parent[w] == v {
return w
}
return -1
}
func (tree *Tree) ELID(u int32) int32 {
return 2*tree.LID[u] - tree.Depth[u]
}
func (tree *Tree) ERID(u int32) int32 {
return 2*tree.RID[u] - tree.Depth[u] - 1
}
func (tree *Tree) build(cur, pre, dep int32, dist int) int32 {
subSize, heavySize, heavySon := int32(1), int32(0), int32(-1)
for _, e := range tree.Tree[cur] {
next, weight := e.to, e.weight
if next != pre {
nextSize := tree.build(next, cur, dep+1, dist+int(weight))
subSize += nextSize
if nextSize > heavySize {
heavySize, heavySon = nextSize, next
}
}
}
tree.Depth[cur] = dep
tree.DepthWeighted[cur] = dist
tree.heavySon[cur] = heavySon
tree.Parent[cur] = pre
return subSize
}
func (tree *Tree) markTop(cur, top int32) {
tree.top[cur] = top
tree.LID[cur] = tree.timer
tree.IdToNode[tree.timer] = cur
tree.timer++
heavySon := tree.heavySon[cur]
if heavySon != -1 {
tree.markTop(heavySon, top)
for _, e := range tree.Tree[cur] {
next := e.to
if next != heavySon && next != tree.Parent[cur] {
tree.markTop(next, next)
}
}
}
tree.RID[cur] = tree.timer
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func min32(a, b int32) int32 {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func max32(a, b int32) int32 {
if a > b {
return a
}
return b
}
func abs32(a int32) int32 {
if a < 0 {
return -a
}
return a
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}