E - Transition Game

[hxrxchang]

https://atcoder.jp/contests/abc296/tasks/abc296_e

問題概要

高橋くんと青木くんのバトル。 要素数Nの数列Aがある。 N回以下のゲームを行う。

1. 青木くんが変換回数を指定する
2. 高橋くんが1以上N以下の整数xを選び黒板に書く。1で指定された回数だけ、黒板に書かれたxを数列A[x]に変換する
3. 操作後、黒板に書かれた数字がそのゲームの回数だったら高橋くんの勝ち。

高橋くんはN回のゲームの中で何回勝てるか求めよ。

解き方

ゲームのルールがわけわかんないが、グラフの閉路に含まれているノードのどれかを選べば、任意の回数移動できることが分かれば解ける。 https://github.com/hxrxchang/atcoder/issues/72 と同じくUnionFindを使って閉路検出をし、その閉路をDFSすることで各ノードが閉路内にいるかどうかが分かる。 閉路内にいるノードは、その成分内のどれかを選んでスタートすれば、任意の回数移動してそこにたどり着ける。

func solve() {
    n := getInt()
    a := getInts()

    graph := make([]int, n + 1)
    for i, v := range a {
        graph[i + 1] = v
    }

    s := newSet[int]()
    uf := newUnionFind(n + 1)

    for i := 1; i <= n; i++ {
        if uf.isSame(i, graph[i]) {
            node := graph[i]
            s.add(i)
            for node != i {
                s.add(node)
                node = graph[node]
            }
        } else {
            uf.unit(i, graph[i])
        }
    }

    fmt.Println(len(s.values))
}

https://atcoder.jp/contests/abc296/submissions/55417962