Codeforces 512 A : Fox And Names
問題リンク : Problem - A - Codeforces
問題概要 :
n個の文字列が与えられる
n個の文字列が辞書順となるような文字の順番が存在するか
あればそれのうちどれか1つを出力せよ
なければ "Impossible" と出力せよ
解法 :
aaab
aaa
のように文字の順番を変えたところでどうしようもないケースは最初にはじいておく
ある文字列とその1つ下の文字列を比較し、最初に異なる部分を見つける
ある文字列を s とし、1つ下の文字列を t とする
異なる場所を i とすると s[i] < t[i]
これらの優先順位を有向辺としてグラフを構築しトポロジカルソートすると良い
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; typedef pair<int,int> ii; vector<int> G[30]; vector<string> arr; vector<ii> edges; bool found[26]; bool used[30]; bool cycle; bool inValid(string a,string b) { if( a == b ) return false; int diff = -1; rep(i,min(a.size(),b.size())) if( a[i] != b[i] ) { diff = i; break; } if( diff == -1 && a.size() > b.size() ) return true; return false; } void add(string a,string b){ if( a == b ) return; int diff = -1; rep(i,min(a.size(),b.size())) if( a[i] != b[i] ) { diff = i; break; } if( diff == -1 ) return; edges.push_back(ii(a[diff]-'a',b[diff]-'a')); } bool visit(int v,vector<int>& order,vector<int>& color){ color[v] = 1; rep(i,G[v].size()){ int e = G[v][i]; if(color[e] == 2)continue; if(color[e] == 1)return false; if(!visit(e,order,color))return false; } order.push_back(v); color[v] = 2; return true; } bool topologicalSort(vector<int>& order){ vector<int> color(26,0); for(int u=0;u<26;u++) if(!color[u] && !visit(u,order,color)) return false; reverse(order.begin(),order.end()); return true; } int main(){ int n; cin >> n; arr.resize(n); rep(i,n) cin >> arr[i]; rep(i,n-1) { if( inValid(arr[i],arr[i+1]) ) { puts("Impossible"); exit(0); } add(arr[i],arr[i+1]); } rep(i,edges.size()) { int src = edges[i].first; int dst = edges[i].second; G[src].push_back(dst); } vector<int> order; if( !topologicalSort(order) ) { puts("Impossible"); exit(0); } rep(i,order.size()) { cout << (char)('a'+order[i]); } puts(""); return 0; }