[백준] 계보 복원가 호석

https://www.acmicpc.net/problem/21276

21276번: 계보 복원가 호석

어제에 이어서 오늘도 호석님에게 고통받을 뻔 했으나 오늘은 잘 넘겼습니다. 위상 정렬을 사용하여 풀 수 있는 문제입니다. 각 가문의 시조를 찾아서 시조를 시작으로 위상정렬을 수행해주면 됩니다. indegree를 0으로 만드는 조상이 바로 부모이므로 indegree를 0으로 만드는 부모의 자식으로 저장해주면 풀 수 있습니다.

 

import sys
from collections import defaultdict, deque

parents = defaultdict(list)
indegree = defaultdict(int)
childs = defaultdict(list)
answer = defaultdict(list)

# sys.stdin = open("input.txt", "r")

input = sys.stdin.readline

# 사람들의 수
n = int(input())

# 사람들의 이름
people = list(map(str, input().split()))

# 이름 순으로 정렬
people.sort()

# 관계의 수
m = int(input())

for _ in range(m):
    child, parent = tuple(map(str, input().split()))
    # 자식의 부모를 저장
    parents[child].append(parent)
    # 부모의 자식을 저장
    childs[parent].append(child)
    # child를 가르키고 있는 조상의 수
    indegree[child] += 1

roots = []

for p in people:
    # 부모가 없는 경우가 가문의 조상이다.
    if not parents[p]:
        roots.append(p)

# 조상의 수 출력
print(len(roots))
# 조상들 출력
print(*roots)

def topologicalSort(root):
    q = deque([root])

    while q:
        cur = q.popleft()
        for child in childs[cur]:
            indegree[child] -= 1
            # indegree가 0으로 만드는 부모가 직계 부모이다.
            if indegree[child] == 0:
                answer[cur].append(child)
                q.append(child)

for r in roots:
    topologicalSort(r)

for p in people:
    print(p, len(answer[p]), *sorted(answer[p]))