あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

AtCoder ABC 142 F - Pure (Go)

irisruneです。ABC-F問題が自力で解けたのはこれで2度目です。

問題

atcoder.jp

グラフ理論です。何を求めればよいかが把握できるかどうかの問題だと思います。

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. 誘導部分グラフのすべての頂点について入次数と出次数が1以上となる。
  2. 入次数と出次数が2以上となる頂点が存在するとき、誘導部分グラフの頂点数よりも長さの短い閉路が存在する。
    1. 誘導部分グラフを構成する辺はすべていずれかの閉路を構成する。

つまり、誘導部分グラフがより長さの短い閉路を含む場合、その閉路を構成する頂点集合を新たな誘導部分グラフの頂点集合とすることができます(当然元のグラフの誘導部分グラフになります)。このとき誘導部分グラフの頂点数は減少し、また長さ2の閉路を構成する頂点集合からなる誘導部分グラフは明らかにすべての頂点の入次数と出次数が1となります。

以上より、自身より長さの短い閉路を含まない(長さが極小の)閉路が条件を満たす誘導部分グラフとなることが示せます。よって以下の手順により問題を解くことができます。

  1. 元のグラフにおいて閉路が含まれるか探索する。
    1. 閉路がない場合は条件を満たす誘導部分グラフは存在しない。
  2. 探索した閉路を構成する頂点集合を誘導部分グラフの頂点集合とおく。
  3. 誘導部分グラフにおいて閉路が含まれるか探索する。
    1. 閉路がない場合は、誘導部分グラフ自身が条件を満たす。
    2. 閉路がある場合は、探索した閉路を構成する頂点集合を誘導部分グラフの頂点集合に置き直す。

ここからは提出コードにおける実装について軽く解説していきます。

まず閉路の探索について、各頂点からBFSで探索を行う形で実装しています。その際、既に訪れた頂点を各探索の頂点ごとに持たせているため少しややこしい実装になっています。計算量はO(N^2)です。

次に極小の閉路を求める部分について、求めた閉路に余分な辺が含まれるかどうかを隣接頂点の集合を用いて判定し、閉路を縮小させていく形で実装しています。計算量はO(N^2)です2

以上より、全体の計算量はO(N^2)となります3

雑記

  • E問題はまだ解けてません。解説ACでもいいと思うのですが、単純に記事を書くことが難しいのが難点です。

  1. 正確にいえば、どの頂点から出発しても元の頂点に戻ってくることができる(どの頂点についてもその頂点を含む閉路が存在する)グラフである必要があります。

  2. ある頂点が隣接頂点の集合に含まれるかの判定にハッシュマップを用いているのでO(N(N+M))にはならないと思います。

  3. 辺の入力を受け取る部分については、辺の数がO(N^2)となるので結局O(N^2)となります。