[백준 / Python 파이썬] 3098번 - 소셜네트워크

[Silver II] 소셜네트워크 - 3098

---

문제 링크

분류

그래프 이론, 구현

문제 설명

소셜 네트워크는 이제 우리 삶의 일부가 되어버렸다. 이러한 소셜 네트워크를 분석하는 김동규 석사과정은 흥미로운 현상을 발견했다. 바로 친구 관계의 수가 급속도로 증가한다는 것이다.

예로부터 우리의 조상님들은 "친구의 친구는 나의 친구"라고 했다. 사람들은 매일 조상님들의 말씀을 따르기 위해서 자신의 친구의 친구 목록을 확인하고, 이를 모두 자신의 친구로 추가한다. 친구 관계는 상대방이 수락을 해야 되고, 총 1일이 걸린다.

예를 들어, A와 B가 친구라면, A는 B가 어제 또는 그 이전에 만든 친구만 볼 수 있다.

모든 친구관계는 대칭이다. 즉, A와 B의 친구라면, B도 A의 친구이다.

김동규가 분석하는 소셜 네트워크에서는 한 번 친구 관계가 맺어졌으면, 이것을 깰 수 없다.

사람의 수와 지금 친구 관계가 주어졌을 때, 모든 사람이 서로 친구가 되는데 걸리는데 며칠이 걸리는지 구하는 프로그램을 작성하시오. 또한, 매일 매일 새로운 친구 관계가 얼마나 생기는지 구해서 출력하시오.

입력

첫째 줄에 사람의 수 N과 처음 친구 관계의 수 M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ N*(N-1)/2)

둘째 줄부터 M개의 줄에는 두 정수 A와 B가 주어진다. (1 ≤ A ≤ N, 1 ≤ B ≤ N, A < B). 이것은 A와 B가 친구라는 것을 의미한다. 항상 모든 사람이 서로 친구가 될 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 모든 사람이 서로 친구가 되는데 며칠이 걸리는지 출력한다. 이 값을 K라고 하자.

다음 K개의 줄에는 몇 명의 새로운 친구 관계가 생기는지, 첫째날부터, K번째 날까지 한 줄에 하나씩 출력한다.

---

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

graph = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

cnt = 0
friends = []
while True:
    answer = 0
    for a in range(1, N + 1):
        answer += len(graph[a])

    if answer == N * (N - 1):
        break

    friend = set()
    for i in range(1, N + 1):
        for j in graph[i]:
            for k in graph[j]:
                if i != k and k not in graph[i]:
                    if i <= k:
                        friend.add((i, k))
                    else:
                        friend.add((k, i))

    for a, b in friend:
        graph[a].append(b)
        graph[b].append(a)

    cnt += 1
    friends.append(len(friend))

print(cnt)
for f in friends:
    print(f)