계보 복원가 호석 (feat. 백준, 21276번)

계보 복원가 호석
https://www.acmicpc.net/problem/21276

21276번: 계보 복원가 호석

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
map<string, vector<string>> arr;
map<string, vector<string>> ans;
map<string, int> check;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M;
    string str1, str2;
    cin >> N;
    for(register int n = 0; n < N; ++n)
        cin >> str1, ans[str1].clear(), check[str1] = 0;
    cin >> M;
    for(register int m = 0; m < M; ++m){
        cin >> str1 >> str2;
        arr[str2].push_back(str1), ++check[str1];
    }
    queue<string> q;
    vector<string> tmp;
    for(auto& name : check)
        if(!name.second)
            q.push(name.first), tmp.push_back(name.first);
    cout << tmp.size() << '\n';
    for(auto& v : tmp)
        cout << v << ' ';
    cout << '\n';
    while(!q.empty()){
        auto name = q.front(); q.pop();
        for(auto& v : arr[name])
            if(--check[v] == 0)
                q.push(v), ans[name].push_back(v);
    }
    for(auto& v : ans){
        cout << v.first << ' ' << v.second.size();
        if(!v.second.empty())
            sort(v.second.begin(), v.second.end());
        for(auto& p : v.second)
            cout << ' ' << p;
        cout << '\n';
    }
	return 0;
}
// *&)*@*

 

반응형

위상정렬을 이용하는 문제입니다.

기존의 문제들과는 다르게 문자열을 이용한다는 점이 색다릅니다.

10/19 결과가 몇번 나왔는데, map의 value가 vector 이므로 이를 정렬해주어야 19/19 결과를 받을 수 있습니다.