結果
問題 | No.1254 補強への架け橋 |
ユーザー |
|
提出日時 | 2023-02-13 02:24:05 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 222 ms / 2,000 ms |
コード長 | 4,215 bytes |
コンパイル時間 | 14,246 ms |
コンパイル使用メモリ | 233,680 KB |
実行使用メモリ | 45,264 KB |
最終ジャッジ日時 | 2024-07-16 08:19:17 |
合計ジャッジ時間 | 26,933 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
ソースコード
package mainimport ("bufio""fmt""os""sort")// int main() {// int N;// cin >> N;// NamoriGraph< int > g(N);// g.read(N);// g.build();// vector< int > ans;// for(auto &e : g.loop_edges) {// ans.emplace_back(e.idx + 1);// }// sort(begin(ans), end(ans));// cout << ans.size() << "\n";// cout << ans << "\n";// }func main() {const INF int = int(1e18)const MOD int = 998244353in := 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.LoopEdges {res = append(res, e.index+1)}sort.Ints(res)fmt.Fprintln(out, len(res))for _, v := range res {fmt.Fprint(out, v, " ")}}type Edge = struct{ from, to, cost, index int }type Graph = [][]Edgetype NamoriGraph struct {Forest []GraphLoopEdges []Edgeg Graphiv [][]intmarkId, id []int}func 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.index)}}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.index] {continue}edgeUsed[e.index] = trueng.LoopEdges = append(ng.LoopEdges, Edge{i, e.to, e.cost, e.index})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.index})tree[ng.id[e.to]] = append(tree[ng.id[e.to]], Edge{ng.id[e.to], ng.id[loop[i]], e.cost, e.index})ng.buildDfs(e.to, loop[i], tree)}}ng.Forest = append(ng.Forest, tree)}}// 頂点 kについて, サイクルの tree_id, 振り直された木の頂点番号 id を返す。func (ng *NamoriGraph) GetId(k int) (treeId, id int) {return ng.markId[k], ng.id[k]}// サイクルの tree_id に付属する頂点 kの`もとの頂点番号`を返す。// 特に GetInvId(tree_id, 0) はサイクルに含まれていたもとの頂点番号を指す。func (ng *NamoriGraph) GetInvId(treeId, k int) int {return ng.iv[treeId][k]}// markDfsfunc (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)}}}// buildDfsfunc (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.index})tree[ng.id[e.to]] = append(tree[ng.id[e.to]], Edge{ng.id[e.to], ng.id[idx], e.cost, e.index})ng.buildDfs(e.to, idx, tree)}}}func max(a, b int) int {if a > b {return a}return b}