天下一プログラマーコンテスト2016予選A C

トポロジカルソートを初めて書いた気がするので記事に残そうと思う

問題

C: 山田山本問題 - 天下一プログラマーコンテスト2016予選A | AtCoder
文字列Ai,BiがN個ずつ与えられる．Ai<=Biとなるようにアルファベット"abc...z"の順序を並び替えたとき，辞書順最小となるアルファベットの順序を出力する問題

解法

トポロジカルソートを使う．AiとBiを左の文字から比較して初めて異なる文字a,bが見つかったときa < bとなるようにアルファベットの順序を並び替えればいい．a→bとしてグラフにするとトポロジカルソートのうち辞書順最小となるものを求めればよくなる．
トポロジカルソートのアルゴリズムは知る限りではDFSとBFSの２種類ある．

• DFSのアルゴリズム

入次数(その頂点に入る矢印の数)が0の頂点からDFSを行う．一番深いところまでたどったら，stackに頂点をpushしていきながら戻ってくる．このようにすることでstackの先頭からトポロジカルソートされた列になっている．

• BFSのアルゴリズム

入次数が0の頂点をすべてqueueに入れBFSを行う．queueから取り出したらその頂点の子の入次数を1減らし，入次数が0になった頂点をqueueに入れる．queueを優先度付きqueueに変えることで辞書順最小のトポロジカルソートを行える．この問題ではこれを使う．

ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)

vector<char> e[256];
int indeg[256];

int main(void) {
    int i, j, n;
    cin >> n;
    REP (i,n) {
        string a, b;
        cin >> a >> b;
        REP (j,min(a.size(),b.size())) if (a[j] != b[j]) {
            e[a[j]].push_back(b[j]);
            indeg[b[j]]++;
            break;
        }
        if (j == b.size() && j < a.size()) {
            cout << -1 << endl;
            return 0;
        }
    }
    priority_queue<char,vector<char>,greater<char>> q;
    for (char c = 'a'; c <= 'z'; c++) if (indeg[c] == 0) {
        q.push(c);
    }
    string ans;
    while (!q.empty()) {
        char c = q.top();
        q.pop();
        for (auto x: e[c]) {
            indeg[x]--;
            if (indeg[x] == 0) q.push(x);
        }
        ans.push_back(c);
    }
    if (ans.size() == 26)
        cout << ans << endl;
    else
        cout << -1 << endl;
    return 0;
}