Help us understand the problem. What is going on with this article?

AtCoder ABC157 D - Friend Suggestions

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))))

https://atcoder.jp/contests/abc157/submissions/10492409

recuraki
AtCoder(緑/水), Codeforces(水/青)をうろうろ (技術士/CCIE/CISSP/CISM/CISA/一陸技/線路/伝送)
http://www.hogetan.net/note/memo/_resume.html
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away