ABC157 D - Friend Suggestions
https://atcoder.jp/contests/abc157/tasks/abc157_d
提出
code: python
n, m, k = map(int, input().split())
ab = list(map(int, input().split())) for _ in range(m)
cd = list(map(int, input().split())) for _ in range(k)
# Union Findっぽい
解答
code: python
N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]
for _ in range(M):
a, b = map(int, input().split())
a, b = a - 1, b - 1
Fa.append(b)
Fb.append(a)
for _ in range(K):
c, d = map(int, input().split())
c, d = c - 1, d - 1
Bc.append(d)
Bd.append(c)
class UnionFind:
def __init__(self, n):
# 親要素のノード番号を格納。parx == xの時そのノードは根(最初は全て根)
self.par = i for i in range(n)
# 木の高さを格納する（初期状態では0）
self.rank = 0 * n
# 人間の数
self.size = 1 * n
# 検索
def find(self, x):
# 根ならその番号を返す
if self.parx == x:
return x
# 根でないなら、親の要素で再検索
else:
# 走査していく過程で親を書き換える(return xが代入される)
self.parx = self.find(self.parx)
return self.parx
# 併合
def union(self, x, y):
# 根を探す
x = self.find(x)
y = self.find(y)
if x == y:
return
# 木の高さを比較し、低いほうから高いほうに辺を張る
if self.rankx < self.ranky:
self.parx = y
self.sizey += self.sizex
else:
self.pary = x
self.sizex += self.sizey
# 木の高さが同じなら片方を1増やす
if self.rankx == self.ranky:
self.rankx += 1
# 同じ集合に属するか判定
def same(self, x, y):
return self.find(x) == self.find(y)
UF = UnionFind(N)
for iam in range(N):
for friend in Fiam:
# 自分と自分の友達を併合
UF.union(iam, friend)
# 友達関係を辿ることで到達できるグループの大きさ - １（自分自身) - 自分の友達の数 -
# 自分の友達候補だがブロック関係の人の数
# 同じ集合に属する人の数
ans = [UF.sizeUF.find(iam) - 1 for iam in range(N)]
for iam in range(N):
# すでに友達関係にある人達を引く
ansiam -= len(Fiam)
for iam in range(N):
for block in Biam:
# ブロック関係にあったら引く
if UF.same(iam, block):
ansiam -= 1
print(*ans, sep=' ')
テーマ
#UnionFind
メモ
ABC157 D - Friend Suggestions