結果
問題 | No.1254 補強への架け橋 |
ユーザー |
|
提出日時 | 2023-03-24 15:20:36 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 269 ms / 2,000 ms |
コード長 | 3,951 bytes |
コンパイル時間 | 11,649 ms |
コンパイル使用メモリ | 223,272 KB |
実行使用メモリ | 43,904 KB |
最終ジャッジ日時 | 2024-09-18 16:28:03 |
合計ジャッジ時間 | 27,078 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
ソースコード
package mainimport ("bufio""fmt""os""sort")func main() {in := bufio.NewReader(os.Stdin)out := bufio.NewWriter(os.Stdout)defer out.Flush()var n intfmt.Fscan(in, &n)g := make([][]Edge, n)for i := 0; i < n; i++ {var a, b intfmt.Fscan(in, &a, &b)a--b--g[a] = append(g[a], Edge{a, b, 1, i})g[b] = append(g[b], Edge{b, a, 1, i})}ng := NewNamoriGraph(g)ng.Build()res := []int{}for _, e := range ng.CycleEdges {res = append(res, e.id+1)}sort.Ints(res)fmt.Fprintln(out, len(res))for _, v := range res {fmt.Fprint(out, v, " ")}}type NamoriGraph struct {// !以环上各个顶点i为根的无向树Trees []Graph// !基环树中在环上的边,边i连接着树的 root i和i+1 (i>=0)CycleEdges []Edgeg Graphiv [][]intmarkId, id []int}type Edge = struct{ from, to, cost, id int }type Graph = [][]Edgefunc NewNamoriGraph(g Graph) *NamoriGraph {return &NamoriGraph{g: g}}func (ng *NamoriGraph) Build() {n := len(ng.g)deg := make([]int, n)used := make([]bool, n)que := []int{}for i := 0; i < n; i++ {deg[i] = len(ng.g[i])if deg[i] == 1 {que = append(que, i)used[i] = true}}for len(que) > 0 {idx := que[0]que = que[1:]for _, e := range ng.g[idx] {if used[e.to] {continue}deg[e.to]--if deg[e.to] == 1 {que = append(que, e.to)used[e.to] = true}}}mx := 0for _, edges := range ng.g {for _, e := range edges {mx = max(mx, e.id)}}edgeUsed := make([]bool, mx+1)loop := []int{}for i := 0; i < n; i++ {if used[i] {continue}for update := true; update; {update = falseloop = append(loop, i)for _, e := range ng.g[i] {if used[e.to] || edgeUsed[e.id] {continue}edgeUsed[e.id] = trueng.CycleEdges = append(ng.CycleEdges, Edge{i, e.to, e.cost, e.id})i = e.toupdate = truebreak}}break}loop = loop[:len(loop)-1]ng.markId = make([]int, n)ng.id = make([]int, n)for i := 0; i < len(loop); i++ {pre := loop[(i+len(loop)-1)%len(loop)]nxt := loop[(i+1)%len(loop)]sz := 0ng.markId[loop[i]] = ing.iv = append(ng.iv, []int{})ng.id[loop[i]] = szsz++ng.iv[len(ng.iv)-1] = append(ng.iv[len(ng.iv)-1], loop[i])for _, e := range ng.g[loop[i]] {if e.to != pre && e.to != nxt {ng.markDfs(e.to, loop[i], i, &sz)}}tree := make(Graph, sz)for _, e := range ng.g[loop[i]] {if e.to != pre && e.to != nxt {tree[ng.id[loop[i]]] = append(tree[ng.id[loop[i]]], Edge{ng.id[loop[i]], ng.id[e.to], e.cost, e.id})tree[ng.id[e.to]] = append(tree[ng.id[e.to]], Edge{ng.id[e.to], ng.id[loop[i]], e.cost, e.id})ng.buildDfs(e.to, loop[i], tree)}}ng.Trees = append(ng.Trees, tree)}}// 给定原图的顶点rawV,返回rawV所在的树的根节点和rawV在树中的编号.func (ng *NamoriGraph) GetId(rawV int) (rootId, idInTree int) {return ng.markId[rawV], ng.id[rawV]}// 给定树的顶点编号root和某个点在树中的顶点编号idInTree,返回这个点在原图中的顶点编号.// GetInvId(root,0) 表示在环上的顶点root在原图中对应的顶点.func (ng *NamoriGraph) GetInvId(rootId, idInTree int) (rawV int) {return ng.iv[rootId][idInTree]}func (ng *NamoriGraph) markDfs(idx, par, k int, l *int) {ng.markId[idx] = kng.id[idx] = *l*l++ng.iv[len(ng.iv)-1] = append(ng.iv[len(ng.iv)-1], idx)for _, e := range ng.g[idx] {if e.to != par {ng.markDfs(e.to, idx, k, l)}}}func (ng *NamoriGraph) buildDfs(idx, par int, tree Graph) {for _, e := range ng.g[idx] {if e.to != par {tree[ng.id[idx]] = append(tree[ng.id[idx]], Edge{ng.id[idx], ng.id[e.to], e.cost, e.id})tree[ng.id[e.to]] = append(tree[ng.id[e.to]], Edge{ng.id[e.to], ng.id[idx], e.cost, e.id})ng.buildDfs(e.to, idx, tree)}}}func max(a, b int) int {if a > b {return a}return b}