読者です 読者をやめる 読者になる 読者になる

yukicoder No.416 旅行会社

問題

No.416 旅行会社 - yukicoder

1~N個の島とM本の橋がある。Q個の橋が順に破壊されていく。島1から到達できなくなるタイミングはいつか。

解法1 union-find木

最後まで壊れなかった橋を初期状態として、逆順に橋を継ぎ足していく。集合データを持たせたunion-find木を使い、結合する集合の片方に島1があるときに、ない方の集合に含まれる島の値を更新していく。集合データの管理には"データ構造をマージする一般的なテク"を使う。

解法2 ダイクストラ法(改変)

解説放送で紹介されたやつ。 順に壊れていく橋のコストを1~Qにしてこれを生存時間と考える。最後まで壊れない橋と島1をinf, その他の島nを-1としておく。行き先の島の生存時間は通る橋と出発点の島の生存時間の短い方をとる。

解法1 コード

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

func main() {
    sc.Split(bufio.ScanWords)
    n := nextInt()
    m := nextInt()
    q := nextInt()
    bridge := make([]nodes, m)
    for i := 0; i < m; i++ {
        bridge[i].a = nextInt()
        bridge[i].b = nextInt()
    }
    crashed := make(map[int]bool)
    crash := make([]nodes, q)

    for i := 0; i < q; i++ {
        crash[i].a = nextInt()
        crash[i].b = nextInt()
        crashed[crash[i].a*1000000+crash[i].b] = true
    }

    uf := makeUnionFind(n + 1)
    // 壊れない橋を追加する
    for i := 0; i < m; i++ {
        if !crashed[bridge[i].a*1000000+bridge[i].b] {
            //fmt.Println("追加1: ", bridge[i].a, bridge[i].b)
            uf.Set(bridge[i].a, bridge[i].b)
        }
    }
    ans := make([]int, n+1)
    // 1とつながっている島
    for _, i := range uf.link[uf.Root(1)] {
        ans[i] = -1
    }
    //fmt.Println("-1ケース, ", ans)

    // 壊れる橋を逆順に追加しながら、つながっているかチェックする
    for i := q - 1; i >= 0; i-- {
        //fmt.Println("追加逆順1:",i,crash[i].a, crash[i].b)

        x := crash[i].a
        y := crash[i].b
        if uf.Same(x, y) {
            continue
        }
        if uf.Same(1, uf.Root(y)) {
            x, y = y, x
        }
        if uf.Same(1, x) {
            for _, h := range uf.link[uf.Root(y)] {
                if ans[h] == 0 {
                    ans[h] = i + 1
                }
            }
        }
        uf.Set(x, y)
    }
    for i := 2; i <= n; i++ {
        fmt.Println(ans[i])
    }
}

type nodes struct {
    a, b int
}

type UnionFind struct {
    par  []int   // 親
    size []int   // 重み
    link [][]int // グループ
}

func makeUnionFind(count int) *UnionFind {
    par := make([]int, count)
    size := make([]int, count)
    link := makeDoubleSliceInt(count, 1)
    for i := 0; i < count; i++ {
        par[i] = i
        size[i] = 1
        link[i][0] = i
    }
    return &UnionFind{par: par, size: size, link: link}
}

func (uf *UnionFind) Root(a int) int {
    for uf.par[a] != a {
        uf.par[a] = uf.par[uf.par[a]]
        a = uf.par[a]
    }
    return a
}

func (uf *UnionFind) Set(a, b int) {
    a = uf.Root(a)
    b = uf.Root(b)
    if a != b {
        if uf.size[a] > uf.size[b] {
            a, b = b, a
        }
        uf.par[a] = b
        uf.size[b] += uf.size[a]
        uf.link[b] = append(uf.link[b], uf.link[a]...)
    }
}

func (uf *UnionFind) Same(a, b int) bool {
    return uf.Root(a) == uf.Root(b)
}

func makeDoubleSliceInt(y, x int) (r [][]int) {
    r = make([][]int, y)
    for i := range r {
        r[i] = make([]int, x)
    }
    return
}

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    i, _ := strconv.Atoi(nextLine())
    return i
}

解法2 コード

package main

import (
    "bufio"
    "container/heap"
    "fmt"
    "os"
    "strconv"
)

const inf int = 1 << 25

func main() {
    sc.Split(bufio.ScanWords)
    // indexと島を合わせるために孤立した島0を加えておく
    n := nextInt() + 1
    m := nextInt()
    q := nextInt()
    bridge := make([]nodes, m)
    crashed := make(map[int]int)
    for i := 0; i < m; i++ {
        bridge[i].a = nextInt()
        bridge[i].b = nextInt()
        crashed[bridge[i].a*1000000+bridge[i].b] = inf
    }
    crash := make([]nodes, q)
    for i := 0; i < q; i++ {
        crash[i].a = nextInt()
        crash[i].b = nextInt()
        crashed[crash[i].a*1000000+crash[i].b] = i + 1
    }

    // グラフ
    g := newGraph(n)
    for i := 0; i < m; i++ {
        a := bridge[i].a
        b := bridge[i].b
        cost := crashed[a*1000000+b]
        g[a] = append(g[a], Edge{to: b, time: cost})
        g[b] = append(g[b], Edge{to: a, time: cost})
    }
    // 改変ダイクストラ
    d := g.dijkstar(n, 1)

    // 最後までつながっている島: -1
    // 最初からつながっている島: 0
    for i := 2; i < n; i++ {
        switch d[i] {
        case inf:
            fmt.Println("-1")
        case -1:
            fmt.Println("0")
        default:
            fmt.Println(d[i])
        }
    }
}

type nodes struct {
    a, b int
}

type Edge struct {
    to   int
    time int
}
type Graph [][]Edge

func newGraph(n int) Graph {
    g := make(Graph, n)
    for i := range g {
        g[i] = make([]Edge, 0)
    }
    return g
}

func (g *Graph) dijkstra(n, s int) []int {
    d := make([]int, n) 
    for i := range d {
        d[i] = -1
    }
    que := make(PriorityQueue, 0)
    heap.Init(&que)
    d[s] = inf
    heap.Push(&que, &Item{node: s, time: inf})
    for que.Len() > 0 {
        p := heap.Pop(&que).(*Item)
        v := p.node
        // 生存時間が島より短い橋は無視する
        if d[v] > p.time {
            continue
        }
        for i := 0; i < len((*g)[v]); i++ {
            e := (*g)[v][i]
            t := min(d[v], e.time) 
            if d[e.to] < t {
                d[e.to] = t
                heap.Push(&que, &Item{time: d[e.to], node: e.to})
            }
        }
    }
    return d
}

// https://golang.org/pkg/container/heap/
// An Item is something we manage in a priority queue.
type Item struct {
    node int // The value of the item; arbitrary.
    time int // The priority of the item in the queue.
    // The index is needed by update and is maintained by the heap.Interface methods.
    index int // The index of the item in the heap.
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    // We want Pop to give us the highest, not lowest, priority so we use greater than here.
    return pq[i].time > pq[j].time
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    item.index = -1 // for safety
    *pq = old[0 : n-1]
    return item
}

func (pq *PriorityQueue) update(item *Item, value int, priority int) {
    item.node = value
    item.time = priority
    heap.Fix(pq, item.index)
}

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    i, _ := strconv.Atoi(nextLine())
    return i
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}