【Python】連結成分の個数をBFS・DFS・Union-Findで求める【ABC284-C・ABC325-C】
本記事はIPFactory Advent Calendar 2023 の9日目の記事として投稿しています。
はじめに
今年の10月にAtCoderのレーティングが800を越え、緑へと色変しました。
普段からAtCoder Beginner Contest(ABC)に楽しく取り組んでいますが、「グラフ探索」という手段を得たことで解ける問題が増え、格段に楽しくなりました。
今回はABCで出題された以下の2問を題材にして、グラフの連結成分の個数をBFS・DFS・Union-Findで求めていきます。
目次
- ABC284-C
- BFS
- DFS
- Union-Find
- ABC325-C
- BFS
- DFS
- Union-Find
ABC284-C
ABC284-Cは、一般的な（普通の？）グラフにおける連結成分の個数を求める問題です。
BFS
BFSは幅優先探索(Breadth First Search)のことです。
BFSの実装はキューを用いると良いと説明されます。そのため、ここではdequeを使用しています。
グラフはdefaultdictを用いてG = defaultdict(list)とすることで、隣接リストの形式で値を保持しています。
from collections import defaultdict,deque N,M = map(int,input().split()) G = defaultdict(list) for _ in range(M): u,v = map(int,input().split()) G[u].append(v) G[v].append(u) visited = [False]*(N+1) ans = 0 for start in range(1,N+1): if visited[start]: continue q = deque() q.append(start) visited[start] = True while q: nowv = q.popleft() for nextv in G[nowv]: if visited[nextv]: continue q.append(nextv) visited[nextv] = True ans += 1 print(ans)
DFS
DFSは深さ優先探索(Depth First Search)のことです。
キューを用いたBFSに対し、DFSにはスタックを用いた実装方法があります。 上記BFSのコードで、
nowv = q.popleft()
の箇所を、
nowv = q.pop()
にするだけで、DFS的な探索順序になるはずです。
また、DFSの実装方法には、再帰関数を用いた簡潔なやり方もあるようです。
from collections import defaultdict import sys sys.setrecursionlimit(10**6) N,M = map(int,input().split()) G = defaultdict(list) for _ in range(M): u,v = map(int,input().split()) G[u].append(v) G[v].append(u) def dfs(nowv): for nextv in G[nowv]: if visited[nextv]: continue visited[nextv] = True dfs(nextv) visited = [False]*(N+1) ans = 0 for start in range(1,N+1): if visited[start]: continue visited[start] = True dfs(start) ans += 1 print(ans)
よく言われる注意点ですが、PyPyは再帰が遅いので、再帰関数を書いた場合はPythonでの提出を考えます。
また、sys.setrecursionlimit()によって再帰回数の上限を増やしておきます。自分は10**6を入れることが多いです。
Union-Find
連結成分の個数を求めるのに、Union-Findというデータ構造を用いることもできます。
ネット上にはUnion-Findの便利なライブラリが落ちており、様々な便利メソッドが搭載されていることがありますが、ここでは最も基本的なfindメソッドとmergeメソッドのみ使います。
経路圧縮・union by rankといった計算量の改善が取り入れられています。
class UnionFind(): def __init__(self,n): self.parent = list(range(n)) self.rank = [0]*(n) def find(self,x): if self.parent[x] == x: return x else: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def merge(self,x,y): rx = self.find(x) ry = self.find(y) if rx == ry: return False if self.rank[rx] < self.rank[ry]: rx,ry = ry,rx self.parent[ry] = rx if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1 return True N,M = map(int,input().split()) UF = UnionFind(N) for _ in range(M): u,v = map(int,input().split()) UF.merge(u-1,v-1) for i in range(N): #ここで苦戦した UF.find(i) print(len(set(UF.parent)))
parent配列に関して、頂点が同じ集合に属しているならば、その頂点のindexには同じ数字（根となる頂点番号）が格納されているはずです。
parent配列に何種類の頂点番号が出現するか数えることで、連結成分の個数を求められると思います。
個人的にUnion-Findに触れて日が浅いので、コード内にも「ここで苦戦した」と書きましたが、mergeの操作を全て完了するだけでは連結成分の個数が求まらないようです。
各頂点に対してfindを行なう、つまり、全ての頂点が根となる頂点番号を指すように書き換える操作が必要となりそうです。
ABC325-C
ABC325-Cも同じく、連結成分の個数を求める問題ですが、グリッド上という点が先ほどと異なります。
BFS
同じくdequeを用いて、popleftを行なうことでキューを実現しています。
この問題では"#"が上下左右斜めに隣接していれば繋がっているとみなされるので、毎回周囲8方向を探索する必要があります。
よく言われることですが8近傍の探索時、
dy = [-1,-1,0,1,1,1,0,-1] dx = [0,1,1,1,0,-1,-1,-1]
以上のような配列を用意すると実装が楽になります。4近傍の場合は数を減らして上下左右だけにしましょう。
from collections import deque H,W = map(int,input().split()) S = [list(input()) for _ in range(H)] visited = [[False]*W for _ in range(H)] dy = [-1,-1,0,1,1,1,0,-1] dx = [0,1,1,1,0,-1,-1,-1] ans = 0 for i in range(H): for j in range(W): if S[i][j] == "." or visited[i][j]: continue q = deque() q.append((i,j)) visited[i][j] = True while q: nowy,nowx = q.popleft() for k in range(8): nexty = nowy + dy[k] nextx = nowx + dx[k] if 0 <= nexty < H and 0 <= nextx < W and S[nexty][nextx] == "#" and not visited[nexty][nextx]: q.append((nexty,nextx)) visited[nexty][nextx] = True ans += 1 print(ans)
DFS
BFSのプログラムのpopleftを、popに書き換えるとDFS的な探索順序になるのは同様なので、省略します。
以下は再帰関数での実装です。
import sys sys.setrecursionlimit(10**6) H,W = map(int,input().split()) S = [list(input()) for _ in range(H)] visited = [[False]*W for _ in range(H)] dy = [-1,-1,0,1,1,1,0,-1] dx = [0,1,1,1,0,-1,-1,-1] def dfs(nowy,nowx): for i in range(8): nexty = nowy + dy[i] nextx = nowx + dx[i] if 0 <= nexty < H and 0 <= nextx < W and S[nexty][nextx] == "#" and not visited[nexty][nextx]: visited[nexty][nextx] = True dfs(nexty,nextx) ans = 0 for i in range(H): for j in range(W): if S[i][j] == "." or visited[i][j]: continue visited[i][j] = True dfs(i,j) ans += 1 print(ans)
UnionFind
このグリッドの問題についても、Union-Findで連結成分の個数を求められると言う人もいます。
苦戦したので非常に拙いですが、グリッドの"#"を頂点と見なし、隣接する8方向に"#"があれば辺があると見なします。
from collections import defaultdict import sys sys.setrecursionlimit(10**6) class UnionFind(): def __init__(self,n): self.parent = list(range(n)) self.rank = [0]*(n) def find(self,x): if self.parent[x] == x: return x else: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def merge(self,x,y): rx = self.find(x) ry = self.find(y) if rx == ry: return False if self.rank[rx] < self.rank[ry]: rx,ry = ry,rx self.parent[ry] = rx if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1 return True H,W = map(int,input().split()) S = [input() for _ in range(H)] M = set() usedGrid = set() dy = [-1,-1,0,1,1,1,0,-1] dx = [0,1,1,1,0,-1,-1,-1] for i in range(H): for j in range(W): if S[i][j] == ".": continue nowId = i*W+j usedGrid.add(nowId) for k in range(8): nowy = i + dy[k] nowx = j + dx[k] if 0 <= nowy < H and 0 <= nowx < W and S[nowy][nowx] == "#": nextId = nowy*W+nowx usedGrid.add(nextId) if not ((nowId,nextId) in M or (nextId,nowId) in M): M.add((nowId,nextId)) d = defaultdict(int) for i,v in enumerate(sorted(list(usedGrid))): d[v] = i N = len(usedGrid) UF = UnionFind(N) for u,v in list(M): UF.merge(d[u],d[v]) for i in range(N): UF.find(i) print(len(set(UF.parent)))
終わりに
ABC284-CとABC325-Cを題材に連結成分の個数を求めてきました。
グラフの連結成分の個数を求める問題は、ABCのC問題でよく見かけると感じており、恐らく典型と呼ばれる部類に属する問題だと思います。ぜひ解いてみてください。
また、最近UnionFindの理解をし始めたところで、実装・使い方の点で明らかな間違いが含まれているかも知れません。本記事のBFS・DFSの実装に関しても大きなミスがあれば、お知らせください。
いずれにしてもより良い方法がありましたらご教示ください。
IPFactory Advent Calendar 2023 8日目はhatomatoくんでした。
