🎃
[Python] ABC399 C Make it Forest
[Python] ABC399 C Make it Forest
目的
- コンテスト中に私自身が回答できなかった問題について、振り返り、理解を深めるための記事です。
- 初心者のため誤解している部分も多いかと思いますが、理解不足の点はその旨記載しています。
問題
自分の回答
- 提出できる回答を作れず。
- 検索した結果、DFSまたはUnion-Findを利用すれば良さそうなところまでは分かったが、取り除く辺を特定する方法を理解できずギブアップ
どうすればよかったのか
そもそも「K 個の連結成分
- 連結成分とは、「部分グラフのうち、極大で連結なもの」らしい。
- 簡単にいうと、ある頂点から見たときに繋がっている範囲の一塊
- 特定の頂点と頂点を繋ぐ辺が全くなければ、別のCということ?
- 入力1を例にすると、頂点1から見た時、Cと言えるのは以下の範囲のはず
-
頂点1から見て、以下の形で繋がった、ひとつのC
-
頂点2,3,4から見ても、同じ形で、頂点1から見た時と同じC
-
- 入力1の場合、4つの頂点に4つの辺を持つ1個の連結成分
が存在するが、どれか1つの辺を削除すれば閉路がなくなり、今回の条件を満たす - これはそういうものとして覚えておくのが良さそう？
- 実際、頂点の数より辺が少なければ閉路ができないのは理解できるので、今後活用できるようにしたい。
- 入力1の場合、M - (N - K) に当てはめると 4 - (4 - 1) で答えの1が導き出せる
Union-Find(素集合データ構造)の使い方について
-
(参考) Union find(素集合データ構造)
-
(まっさらなところから)各頂点に対して、辺を追加していく。
- 入力1を例にすると、最初に存在するのは、1,2,3,4 の4つのグループ
- 1と2を繋ぐ辺を追加
- 1&2,3,4 の3グループ
- 1と3を繋ぐ辺を追加
- 1&2&3,4 の2グループ
- 2と4を繋ぐ辺を追加
- 1&2&3&4 の1グループ
- (2と1がすでに同じグループ、かつ2の親は1であるため、4も1を親としたグループに入る)
- 3と4を繋ぐ辺を追加
- すでに3と4は(1が親の)同じグループに所属しており、追加してしまうと閉路ができてしまうため、削除したい （★今回の問題ではこの数を求めたい）
- イメージとしては以下のような感じだと思う
-
参考ページの「Union-Find木の実装(ランク無し)」をもとに実装してみる
n, m = map(int, input().split())
uv = [list(map(int, input().split())) for i in range(m)]
class UnionFind:
def __init__(self, n):
# 最初は全て独立している
self.par = list(range(n))
def root(self, x):
if self.par[x] == x:
return x
else:
self.par[x] = self.root(self.par[x])
return self.par[x]
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
self.par[x] = y
ans = 0
union = UnionFind(n)
for i in range(m):
u = uv[i][0] - 1
v = uv[i][1] - 1
if union.same(u, v):
ans += 1
else:
union.unite(u, v)
print(ans)
補足
- 今回は自分自身の理解のためUnionFindクラスを実装したが、AtCoderのライブラリでUnion-Findを簡単に利用できる。
- pythonの場合、以下が該当する
- 使ってみた
from atcoder.dsu import DSU
n, m = map(int, input().split())
uv = [list(map(int, input().split())) for i in range(m)]
ans = 0
union = DSU(n)
for i in range(m):
u = uv[i][0] - 1
v = uv[i][1] - 1
if union.same(u, v):
ans += 1
else:
union.merge(u, v)
print(ans)
Discussion