[BOJ / C++] 계보 복원가 호석 (위상정렬)

문제링크: https://www.acmicpc.net/problem/21276

 

1. 코드

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    map<string, int> n2i;
    map<int, string> i2n;

    vector<string> name(n);
    for (int i = 0; i < n; i++) {
        cin >> name[i];
    }
    sort(name.begin(), name.end());

    for (int i = 0; i < n; i++) {
        n2i[name[i]] = i;
        i2n[i] = name[i];
    }
    
    vector<int> deg(n, 0);
    vector<vector<int>> adj(n);

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

        int a = n2i[nm1];
        int b = n2i[nm2];

        adj[b].push_back(a);
        deg[a]++;
    }

    // 시조 찾기
    vector<string> root;
    queue<int> Q;

    for (int i = 0; i < n; i++) {
        if (deg[i] == 0) {
            root.push_back(i2n[i]);
            Q.push(i);
        }
    }

    // 위상정렬 정보 저장
    vector<vector<int>> tree(n);

    while (!Q.empty()) {
        int cur = Q.front(); Q.pop();
        for (int nxt : adj[cur]) {
            deg[nxt]--;
            if (deg[nxt] == 0) {
                tree[cur].push_back(nxt);
                Q.push(nxt);
            }
        }
    }

    // 출력
    cout << root.size() << '\n';
    
    sort(root.begin(), root.end());
    for (auto r : root) {
        cout << r << ' ';
    }
    cout << '\n';

    for (int i = 0; i < n; i++) {
        cout << i2n[i] << ' ' << tree[i].size() << ' ';
        vector<string> tmp;
        for (int p : tree[i]) {
            tmp.push_back(i2n[p]);
        }
        sort(tmp.begin(), tmp.end());

        for (string& p : tmp) {
            cout << p << ' ';
        }
        cout << '\n';
    }   
}

 

 

2. 시간복잡도

위상정렬에는 \(O(v+e)\)가 걸리고 출력에는 \(O(n \times n \log n) = 10^{7} < 10^{8}\)이므로 시간제한 1초 내에 통과 가능하다.

 

 

3. 분석

각각을 lexical order로 설정해야하는 것은 sort를 통해서 해결한다. n2i와 i2n을 통해 각각을 변환할 수 있도록 준비한다. adjacent list에서 부모 -> 자식 방향으로 인접리스트를 구현하는데 그래야 시조의 개수를 바로 셀 수 있기 때문이다. 이후 위상정렬을 하고 ` deg[nxt] == 0 `이면 cur이 부모 nxt가 자식이므로 해당 정보를 tree에 저장해준다. 출력할 때는 lexical order 출력에 주의한다.