백준 21276번 : 계보 복원가 호석 - 위상정렬 C++ 코드

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

21276번: 계보 복원가 호석

 

#include <bits/stdc++.h>
using namespace std;


int n, m, cnt=1;
map<string, int> dic;
string node[1001];

set<string> child[1001];
vector<int> adj[1001];
int degree[1001];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        node[cnt] = s;
        dic[s] = cnt++;
    }

    cin >> m;
    for (int i = 0; i < m; i++) {
        string x, y;
        cin >> x >> y;

        adj[dic[y]].push_back(dic[x]);
        degree[dic[x]]++;
    }


    queue<int> Q;

    int K = 0;
    vector<string> parent;
    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            K++;
            Q.push(i);
            parent.push_back(node[i]);
        }
    }
    
    sort(parent.begin(), parent.end());
    cout << K << '\n';
    for (int i = 0; i < K; i++) {
        cout << parent[i] << ' ';
    }
    cout << '\n';

    
    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for (auto nx : adj[x]) {
            if (--degree[nx] == 0) {
                //차수가 0이 되는 노드들만 x의 자식이다.
				child[x].insert(node[nx]);
                Q.push(nx);
            }
        }
    }

    for (auto x : dic) {
        cout << x.first << ' ';

        cout << child[x.second].size() << ' ';

        for (auto c : child[x.second]) {
            cout << c << ' ';
        }
        cout << '\n';
    }

   
    return 0;
}

백준 21276번