Python3で解く AtCoder Beginner Contest 177 D - Friends

グラフの連結

目次

概要

問題
1. 人いる。
1. 個の友人関係情報が与えられる。
1. 直接友人でなくても、友人の友人は友人であるとする。
1. この時に、友人同士を含まないようにするグルーピングを考える。
1. 最小のグループ数は？

---

解くときに考えた内容

BFS

• 強い人はUnion-Findとすぐわかる。
• 直感的には最大グループ人数が求める答え。
  • 人のグループが最大とすると、x人をそれぞれ違うグループにする事が課題になる。それ以下の人数のグループは、それに応じて分ければいいだけなので。
• 今回はBFSで、各頂点から最短で繋がっている部分の距離をはかる。（正確には一人分を1として距離+1（自分自身だけでも1としたいから））
• 1人のグループなら1となって、2人なら1+1で2となるように実装する。
• これは単純にBFSで、 (事前に隣接行列は作る。)
  • 各頂点ごとに調べます。
  • 頂点に行った事があるかないかを記録する。
  • 行った事がある頂点だったら、次の頂点へ。
  • 行った事がない頂点だったら、キューに加えて、キューがなくなるまで、探索。探索した頂点は行ったと記録する。
  • 行った事がない場所には隣接行列から違う頂点に行った事がなければ、行く。その時に「距離として（グループ内の友人数として）」+1する。

Union-Find

よく知らなかったけど、このページ見た方が多分わかる。

atcoder.jp

とりあえず、ちょっと変形して実装し直して、グループの人数が増えるとparentが負になって行くので、戻して最大の値をとれば、答え。 もうちょっとちゃんと説明できるように別記事にする。

---

コード

BFS

n, m = map(int, input().split())
# 隣接行列は作っておく
g = [[] for i in [0]*(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
def bfs(n, m, adj):
    visited = [0 for i in [0]*(n+1)]
    ans = 1
    for i in range(n+1):
        if visited[i]:
            continue
        Q = deque([i])
        group_friend = 1
        while Q:
            q = Q.popleft()
            visited[q] = 1
            link = adj[q]
            for j in link:
                if visited[j]:
                    continue
                visited[j] = 1
                group_friend += 1
                Q.append(j)
        ans = max(ans, group_friend)
    print(ans)  
bfs(n, m, g)

Union-Find

def find(target):
    if parent[target] < 0:
        return target
    else:
        parent[target] = find(parent[target])
        return parent[target]

def is_same(x, y):
    return find(x) == find(y)

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x == root_y:
        return
    if parent[root_x] > parent[root_y]:
        root_x, root_y = root_y, root_x
    parent[root_x] += parent[root_y]
    parent[root_y] = root_x

# 今回これ使わないけど、どこに誰がいるのかはこれでわかる
def members(n, x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

def get_size(x):
    return -parent[find(x)]

def get_root():
    return [i for i, root in enumerate(parent) if root < 0]
n, m = map(int, input().split())
parent = [-1 for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    union(a, b)
ans = 0
for i in range(n):
    ans = max(ans, get_size(i))
print(ans)

---

書籍

最近ポチった書籍

• ゼロからつくるPython機械学習プログラミング入門

機械学習スタートアップシリーズ ゼロからつくるPython機械学習プログラミング入門 (KS情報科学専門書)

アルゴリズムとは関係ないが、一応機械学習も生業としているので、関連書籍は目を通すようにしている。 強いていうならば、第3章の数学のおさらいの最適化・確率あたりは関連がある。その他、回帰分析・分類・ニューラルネットワーク・強化学習・教師なし学習とかなり幅広く、初学者が一通り学ぶには良さそうである。これは別記事で紹介する予定である。

• 実用的でないPythonプログラミング

実用的でないPythonプログラミング: 楽しくコードを書いて賢くなろう!

バカ売れしているのか、アマゾンでは値段があがっている。自分は、予約していたのに来ないので、楽天で購入した。 内容としては、面白いテーマの物が多く、pygletなどを使って描画もあるような内容が結構推されているが、アルゴリズムに関する内容もある。特に前半は文字列を操作して暗号解読であったり、アナグラム・回文といったものが扱われているので勉強になる。遺伝的アルゴリズムも面白く金庫破りの実装は非常に参考になった。

blacktanktop.hatenablog.com

• 問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも結構読みやすいのではないかと期待。（というのもけんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているので）
投稿時点では、まだ発売前だけど、すでにベストセラー。予約しておかないとすぐ手元に来ないかも!?と思って速攻ポチった。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

drken1215.hatenablog.com

アルゴリズムの参考書籍

• プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。（AtCoderもそんな感じのリスト作って欲しい） ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。（AOJも解いているので、記事にしていこうかなぁ）

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造