ACL C - Connect Cities

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
INF = float('inf')


class UnionFind:
    def __init__(self, N):
        self.tree = [-1 for _ in range(N)]

    def root(self, N):
        if self.tree[N] < 0:
            return N
        self.tree[N] = self.root(self.tree[N])
        return self.tree[N]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.tree[x] > self.tree[y]:
            x, y = y, x
        self.tree[x] += self.tree[y]
        self.tree[y] = x

    def size(self, x):
        return -self.tree[self.root(x)]


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    AB = [il() for _ in range(M)]
    uf = UnionFind(N)

    for a, b in AB:
        uf.unite(a-1, b-1)

    ret = set()
    for n in range(N):
        ret.add(uf.root(n))
    print(len(ret)-1)


if __name__ == '__main__':
    main()

考え方

グループ分けを行うUnionFind木の典型問題です。

• 回答概要
  • 道路が繋がっている行き来できる都市群を１つのグループとする
  • 全ての都市を行き来するために、必要な道路はグループの数 - 1つ
  • グループの数を求めるには、UnionFind木を使用する

---

まず、全ての都市に行き来するために、必要な道路の数を考えます。
既に道路が繋がっている都市を１つのグループと考えると、
全てのグループに道路が繋がっていれば、全ての町に移動可能になります。
そのため、必要な道路の数はグループの数 - 1つです。

次にグループの求め方を考えます。
グループ分けにはUnionFind木が最適です。

Union-Find木の解説と例題 - Qiita

UnionFind木で各都市を繋げて、親の数を求めます。
親の数がそのままグループの数となるため、
後は親の数 - 1を回答とします。