2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

AtCoder ABC157 D - Friend Suggestions

Last updated at Posted at 2020-03-02

概要

割愛しつつ。

まず、ある人に注目した時、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))))

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?