import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
name = sorted(input().split())
M = int(input())
child = {i:set() for i in name}
realchild = {i:set() for i in name}
indegree = {i:0 for i in name}
for i in range(M):
c,p = input().split()
child[p].add(c)
indegree[c] += 1
father = []
dq = deque()
for i in name: #시조
if not indegree[i]:
father.append(i)
dq.append(i)
while dq:
now = dq.popleft()
for next in child[now]:
indegree[next] -= 1
if indegree[next]:
continue
dq.append(next)
realchild[now].add(next)
print(len(father))
print(" ".join(father))
for i in name:
print(i,end=" ")
print(len(realchild[i]),end=" ")
for c in sorted(realchild[i]):
print(c,end=" ")
print()
문제 설명이 약간 난해하게 되어있었는데 결국 전형적인 위상정렬 문제이다.
요약하면,
1. 각 사람들에 대해서 각각의 자손들을 child list에 넣어주고, 자손들은 indegree를 1씩 늘린다.
2. indegree가 0인 사람이 곧 시조이며, father list에 넣어준다.
3. BFS로 위상정렬을 하는 과정에서 각 자식들의 indegree를 1 뺐을때 0이 되는 경우 realchild에 추가한다.
4. father와 모든 사람들에 대한 realchild를 출력한다.
오늘의 교훈) 위상정렬은 매우 편리하다.