AtCoder ABC 142 F - Pure (Go)
irisruneです。ABC-F問題が自力で解けたのはこれで2度目です。
問題
グラフ理論です。何を求めればよいかが把握できるかどうかの問題だと思います。
package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextStr() string { sc.Scan() return sc.Text() } func nextInt() int { sc.Scan() i, e := strconv.Atoi(sc.Text()) if e != nil { panic(e) } return i } type vertex struct { num int prev *vertex visited []bool } func findCycle(n int, adj []map[int]struct{}) ([]int, bool) { for i := 1; i <= n; i++ { queue := make([]vertex, 0) queue = append(queue, vertex{i, nil, make([]bool, n+1)}) for len(queue) > 0 { v := queue[0] queue = queue[1:] for x := range adj[v.num] { if v.visited[x] { ret := []int{v.num} for v.num != x { ret = append(ret, v.prev.num) v = *v.prev } return ret, true } visited := make([]bool, n+1) copy(visited, v.visited) visited[v.num] = true queue = append(queue, vertex{x, &v, visited}) } } } return []int{}, false } func main() { sc = bufio.NewScanner(os.Stdin) sc.Buffer(make([]byte, 0), 1000000001*3) sc.Split(bufio.ScanWords) n, m := nextInt(), nextInt() adj := make([]map[int]struct{}, n+1) for ni := 0; ni <= n; ni++ { adj[ni] = make(map[int]struct{}) } for i := 0; i < m; i++ { a, b := nextInt(), nextInt() adj[a][b] = struct{}{} } cycle, ok := findCycle(n, adj) if !ok { fmt.Println(-1) return } for i := 0; ; i++ { if i >= len(cycle)-1 { break } for j := i + 1; ; j++ { if j >= len(cycle) { break } _, ok := adj[cycle[i]][cycle[j]] if ok { cycle = cycle[i : j+1] i, j = 0, j-i } } } fmt.Println(len(cycle)) for _, c := range cycle { fmt.Println(c) } }
結論だけ言えば、元のグラフに含まれる長さが極小となる閉路が求める誘導部分グラフになります。ひとまずこれを示してみます。
まず、すべての頂点について入次数と出次数が1以上になるためにはグラフが閉路を持つ必要があります。1また、入次数と出次数がちょうど1となるためにはグラフが単一の閉路で構成される必要があります。
ここで誘導部分グラフの性質について考えてみます。元のグラフに含まれるある閉路について、その閉路を構成する頂点集合を誘導部分グラフの頂点集合とした場合、以下のことがいえます。
- 誘導部分グラフのすべての頂点について入次数と出次数が1以上となる。
- 入次数と出次数が2以上となる頂点が存在するとき、誘導部分グラフの頂点数よりも長さの短い閉路が存在する。
- 誘導部分グラフを構成する辺はすべていずれかの閉路を構成する。
つまり、誘導部分グラフがより長さの短い閉路を含む場合、その閉路を構成する頂点集合を新たな誘導部分グラフの頂点集合とすることができます(当然元のグラフの誘導部分グラフになります)。このとき誘導部分グラフの頂点数は減少し、また長さ2の閉路を構成する頂点集合からなる誘導部分グラフは明らかにすべての頂点の入次数と出次数が1となります。
以上より、自身より長さの短い閉路を含まない(長さが極小の)閉路が条件を満たす誘導部分グラフとなることが示せます。よって以下の手順により問題を解くことができます。
- 元のグラフにおいて閉路が含まれるか探索する。
- 閉路がない場合は条件を満たす誘導部分グラフは存在しない。
- 探索した閉路を構成する頂点集合を誘導部分グラフの頂点集合とおく。
- 誘導部分グラフにおいて閉路が含まれるか探索する。
- 閉路がない場合は、誘導部分グラフ自身が条件を満たす。
- 閉路がある場合は、探索した閉路を構成する頂点集合を誘導部分グラフの頂点集合に置き直す。
ここからは提出コードにおける実装について軽く解説していきます。
まず閉路の探索について、各頂点からBFSで探索を行う形で実装しています。その際、既に訪れた頂点を各探索の頂点ごとに持たせているため少しややこしい実装になっています。計算量はです。
次に極小の閉路を求める部分について、求めた閉路に余分な辺が含まれるかどうかを隣接頂点の集合を用いて判定し、閉路を縮小させていく形で実装しています。計算量はです2。
以上より、全体の計算量はとなります3。
雑記
- E問題はまだ解けてません。解説ACでもいいと思うのですが、単純に記事を書くことが難しいのが難点です。