[ 21276 ] [ 위상 정렬 ] 계보 복원가 호석

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

21276번: 계보 복원가 호석

 

---

풀이 과정

---

1. 이름과 연결된 자식들의 정보를 저장해 둔다.
   • 자식-(부모 or 조상)이 연결되어 있다면, 자식의 진입차수를 1 증가시켜 준다.
   • 단, 여기서 부모가 조상일수도 있음.
2. 초기 큐에는 각 가문의 시조들을 저장해 둔다.
   
   • 진입차수가 0인 이름들이 각 가문의 시조들이다.
3. 큐에서 한명씩 빼주면서 연결된 자식들의 진입차수를 1씩 감소시킨다.
   1. 진입차수가 0이 된다면, 해당 자식은 직전에 큐에서 빼준 인원의 자식이기 때문에 따로 저장해 두고, 해당 자식은 큐에 삽입하여 준다.
4. 출력 형식에 맞추어서 출력시켜주면 된다.

---

소스 코드

---

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()
N = int(input())
people = set(input().split())
child = {person:[] for person in people}
edge = {person:[] for person in people}
indegree = {person:0 for person in people}
father = []

M = int(input())
for _ in range(M):
    a, b = input().split()
    indegree[a] += 1
    edge[b].append(a)
    
queue = deque()
for person in people:
    if indegree[person] == 0:
        queue.append(person)
        father.append(person)
        
while queue:
    node = queue.popleft()
    for next_node in edge[node]:
        indegree[next_node] -= 1
        if indegree[next_node] == 0:
            queue.append(next_node)
            child[node].append(next_node)

print(len(father))
print(*sorted(father))
for name in sorted(list(people)):
    print_str = name + " " + str(len(child[name]))
    if len(child[name]) != 0:
        print_str += (" " + " ".join(sorted(child[name])))
    print(print_str)