AtCoder AGC 039 B - Graph Partition (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。今週は台風の影響で公式コンテストが開催されないそうです。

問題

どのような場合に条件を満たす分割が可能か、どのようにして分割の最大数を求めるかがポイントになります。

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
}

func solve(n, iMin int, adj [][]int) int {
    vertexes := make([]int, n)
    count := 1
    vertexes[iMin] = count
    queue := make([]int, 0)
    queue = append(queue, iMin)
    for {
        for len(queue) > 0 && vertexes[queue[0]] == count {
            u := queue[0]
            queue = queue[1:]
            for v, a := range adj[u] {
                switch {
                case a == 0:
                    continue
                case vertexes[v] == 0:
                    vertexes[v] = count + 1
                    queue = append(queue, v)
                case vertexes[v] == count-1 || vertexes[v] == count+1:
                    continue
                default:
                    return -1
                }
            }
        }
        if len(queue) == 0 {
            break
        }
        count++
    }
    return count
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n := nextInt()

    adj := make([][]int, n)
    for i := range adj {
        adj[i] = make([]int, n)
        s := nextStr()
        for j, r := range s {
            if r == '1' {
                adj[i][j] = 1
            }
        }
    }

    /*
        divMin := n
        iMins := make([]int, 0)
        for i := range adj {
            div := 0
            for _, a := range adj[i] {
                div += a
            }
            switch {
            case div < divMin:
                divMin = div
                iMins = []int{i}
            case div == divMin:
                iMins = append(iMins, i)
            }
        }
    */

    ans := -1
    /*
        for _, iMin := range iMins {
            cnt := solve(n, iMin, adj)
            if cnt > ans {
                ans = cnt
            }
        }
    */
    for i := 0; i < n; i++ {
        cnt := solve(n, i, adj)
        if cnt > ans {
            ans = cnt
        }
    }
    fmt.Println(ans)
}

まず、条件を満たす分割が可能となるのはグラフが2分グラフである場合のみです。何故なら、 $V_1,V_3,\ldots$ の各集合間を結ぶ辺は存在せず、また各集合内の頂点を結ぶ辺も存在しないことが条件となるためです（ $V_2,V_4,\ldots$ についても同様のことがいえます）。

分割の最大数は解説の通りグラフの直径をワーシャルフロイド法などにより求めてしまえば簡単に求めることができます。今回は2分グラフの判定法を流用する形で求めましたが、思い違いにより手こずってしまいました。

最初は次数が最小の任意の頂点のみからなる集合 $V_1$ を始点とすれば最大の分割が得られると考えていました。しかしその提出はWAでした。そのため次に次数が最小の頂点が複数ある場合、それぞれを $V_1$ とおいたときの分割数の最大値を求めることにしましたが、これもまたWAでした。実は以下のようなグラフがコーナーケースになってしまいます。