土下座しながら探索中

主に競技プログラミング

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;
}