오름차순으로 출력해야하니까 주어진 사람들의 이름들을 정렬합시다. 그러면 번호 이름꼴로 저장할 수 있습니다. 여기에 이름 번호꼴도 처리할 수 있도록 Map을 선언하면 더 편리합니다.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder bw = new StringBuilder();
int N = Integer.parseInt(br.readLine());
String[] S = new String[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) S[i] = st.nextToken();
Arrays.sort(S);
// 이름이 주어지면 사전순으로 정렬했을 때 몇 번째인지 반환하는 map
Map<String, Integer> m = new HashMap<>();
for (int i = 0; i < N; i++) m.put(S[i], i);
// 위상정렬을 위해 어떤 정점에 들어오는 간선의 개수 저장
// X -> Y : X의 조상 중 Y가 있다
// 가장 위에 있는 조상부터 고를 수 있도록 간선의 방향은 Y -> X가 됨
int[] indegree = new int[N];
boolean[][] adj = new boolean[N][N];
int M = Integer.parseInt(br.readLine());
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int u = m.get(st.nextToken());
int v = m.get(st.nextToken());
adj[v][u] = true;
indegree[u]++;
}
// 들어오는 간선이 없는 정점은 시조
int cnt = 0;
for (int i = 0; i < N; i++)
if (indegree[i] == 0) cnt++;
bw.append(cnt).append("\n");
Queue<Integer> q = new LinkedList<>();
// 사전순으로 출력해야하므로 정렬된 배열 S의 순서에 맞게 큐에 삽입
for (int i = 0; i < N; i++) if (indegree[i] == 0) {
bw.append(S[i]).append(" ");
q.offer(i);
}
bw.append("\n");
// i번째 정점의 자식들을 사전순으로 정렬하기 위해서 우선순위 큐 사용
ArrayList<PriorityQueue<Integer>> T = new ArrayList<>(N);
for (int i = 0; i <= N; i++) T.add(new PriorityQueue<>());
for (int i = 0; i < N; i++) {
// indegree가 0인 가장 조상인 정점을 뽑는다
int here = q.poll();
for (int there = 0; there < N; there++) if (adj[here][there]) {
indegree[there]--;
// 새롭게 indgree가 0인 정점이 있으면 큐에 삽입
// 마찬가지로 S는 정렬되어 있으므로 큐에는 오름차순으로 들어감
if (indegree[there] == 0) {
q.offer(there);
T.get(here).offer(there);
}
}
}
for (int i = 0; i < N; i++) {
bw.append(S[i]).append(" ");
bw.append(T.get(i).size()).append(" ");
PriorityQueue<Integer> pq = T.get(i);
while (!pq.isEmpty()) bw.append(S[pq.poll()]).append(" ");
bw.append("\n");
}
System.out.print(bw);
}
}