codeforces 510C Fox And Names 拓撲排序

codeforces 510C Fox And Names 拓撲排序

傳送門:cf 510D

給定n個字符串，問能否存在這樣的字母表，使得字符串的排序滿足字典序。即依據新的字母表，排序滿足字典序大小。

假設滿足字典序，則我們可以依據已有的字符串得出各字母之間的大小關系，然後通過拓撲排序來判斷是否存在可行解，輸出任意解，因此只需要判斷是否存在解即可。

/******************************************************
 * File Name:   a.cpp
 * Author:      kojimai
 * Create Time: 2015年02月03日 星期二 00時32分13秒
******************************************************/

#include
#include
#include
#include
#include
#include
using namespace std;
#define FFF 105
char s[FFF][FFF],ans[30];
int in[FFF];
bool link[26][26];

queue p;
bool solve() { // 通過拓撲排序判定是否存在可行解
	int cnt = 0;
	for(int i = 0;i < 26;i++) {
		if(in[i] == 0) {
			p.push(i);
			ans[cnt++] = 'a' + i;
		}
	}	
	while(!p.empty()) {
		int now = p.front(); p.pop();
		for(int i = 0;i < 26;i++) {
			if(link[now][i]) {
				in[i]--;
				if(in[i] == 0) {
					p.push(i);
					ans[cnt++] = 'a' + i;
				}
			}
		}
	}
	ans[26] = '\0';
	if(cnt < 26)
		return false;
	else
		return true;
}

int main() {
	int n;
	cin >> n;
	for(int i = 0;i < n;i++)
		cin >> s[i];
	bool flag = true;
	memset(link,false,sizeof(link));
	memset(in,0,sizeof(in));
	for(int i = 0;i < n - 1 && flag;i++) {
		bool ok = false;
		int l1 = strlen(s[i]),l2 = strlen(s[i+1]);
		for(int j = 0;j < l1 && j < l2 && !ok;j++) {
			if(s[i][j] != s[i+1][j]) { //同一位置的字母不同，則字典序的大小可以比較出來了，即對應字母的相對大小可知
				ok = true;
				if(!link[s[i][j]-'a'][s[i+1][j]-'a']) {
					in[s[i+1][j]-'a']++;
					link[s[i][j]-'a'][s[i+1][j]-'a'] = true;
				}
			}
		}	
		if(!ok && l1 > l2)
			flag = false;//某兩個字符串前綴完全相同，但是第一個字符串長度較大，則兩字符串必定不滿足字典序
	}	
	if(!flag) {
		printf("Impossible\n");
	}
	else {
		flag = solve();
		if(!flag)
			printf("Impossible\n");
		else
			printf("%s",ans);
	}
	return 0;
}