天下一プログラマーコンテスト2016予選A C - 山田山本問題

解説

a,...,zを頂点としてトポロジカルソート。

頂点数が少ないので、O(N³)のアルゴリズムでOK。

トポロジカルソートの参考サイト。

Topological sort

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
bool G[26][26]; // 頂点iがjより前
bool used[26];
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  FOR(i,0,N) {
    string s, t; cin >> s >> t;
    int j;
    for(j = 0; j < s.length() && j < t.length() && s[j] == t[j]; j++);
    if(j == t.length()) {
      cout << -1 << endl;
      return 0;
    }
    if(j == s.length()) continue;
    G[s[j]-'a'][t[j]-'a'] = true;
  }
  // トポロジカルソート
  // 頂点数が少ないのでO(26^3)でできる
  // O(E+V)のアルゴリズムもあり
  string ans = "";
  FOR(i,0,26) {
    int u = 0;
    // 頂点uに注目
    bool ok = true;
    for(;u < 26;u++) {
      if(used[u]) continue;
      ok = true;
      // v -> uの辺がなければ答えについか
      FOR(v,0,26) if(G[v][u]) ok = false;
      if(ok) break;
    }
    if(!ok) {
      cout << -1 << endl;
      return 0;
    }
    used[u] = true;
    ans += char(u + 'a');
    FOR(v,0,26) G[u][v] = false;
  }
  cout << ans << endl;
  return 0;
}