https://atcoder.jp/contests/abc157/tasks/abc157_d
概要
割愛しつつ。
まず、ある人に注目した時、SNS全体の人は以下のいずれかに分類される。
- a. 自分自身
- b. 友達
- c. 友達の友達のつながりで到達できる人
- d. 他人(友達経由で到達できない人)
※ブロックしうるのはc, dの人だけである。(条件より友達をブロックして/されていることはない)
各人について、ブロックしていないcの人数を述べよ。
アプローチ
友達はいわばグループであるので、求めたい人数というのは、$自分の所属するグループの人数 - a - b - cのうちブロックしている人数$である。
まず、グループの分類はDFSで求められる。あるノードを取り、そのノードをそのグループ番号とする。そのノードからひたすらノードを追っていき、その番号を付与していくとともに数を数える。たどり終わったら、その番号のノード数を記録する。これをすべてのノードの探索が終わるまで繰り返す。
あるグループのノード数は$a+b+c$である。
ノード間の辺を読み取る際に、各ノードが辺を何本持つかをカウントしておく。これは$b$に他ならない。
これを、グループのノード数から引くことで、$c$を得られた。しかし、これにはブロックされている関係を含む。このため、ブロックされている関係x,yにおいて以下の処理を行う。xとyが同じグループに所属しているなら、x,yのそれぞれの友達候補数を-1する。
※尚、万一「友達関係であってもブロック」できてしまうと上記で数を減らしすぎてしまうが、今回は制約上、これは発生しない
コード
from collections import deque
n, m, k =map(int, input().split())
directcount = [0] * n # node_iが直接接続しているノードの数
visited = [-1] * n # nodeの色,
colorcount = [-1] * n # 各色が何個のノードを持つか
# グラフの初期化
g = []
for _ in range(n):
g.append(deque(list()))
# グラフの生成
for i in range(m):
a, b = map(int, input().split())
a, b = a - 1, b - 1 # 1origin -> 0 origin
g[a].append(b)
g[b].append(a)
# 直接接続されているノードの数
directcount[a] += 1
directcount[b] += 1
# dfs 連結したグラフごとにそのグラフの最初に探索したnodeの色に染める
q = deque(list()) #探索キュー
for i in range(n):
q.append(i)
color = i
cnt = 1
while len(q) > 0:
nextnode = q.popleft() # 次の探索
if visited[nextnode] != -1:
continue
visited[nextnode] = color
q.extend(g[nextnode]) # nextnodeの辺を足す
cnt += 1
# 探索が終わったらその色のノードの数を記録
colorcount[color] = cnt - 1
# res[i] = ノードの色, その色のノードの数 - そのノードが直接接続しているノード数 - 自分自身(1) で初期化する
res = [[visited[i], colorcount[visited[i]] - (directcount[i] + 1)] for i in range(n)]
# ブロックリスト
for i in range(k):
c, d = map(int, input().split())
c, d = c - 1, d - 1 # 1 origin -> 0 origin
# ブロック関係が同じ色だとするなら
if res[c][0] == res[d][0]:
# 友達になれると思っていた数を1つ減らす
res[c][1] -= 1
res[d][1] -= 1
# 結果の表示
print(" ".join(list(map(lambda x: str(x[1]), res))))
