UVa 200

題目

http://domen111.github.io/UVa-Easy-Viewer/?200

給定一群字串，這群字串是依照某種字母順序的排序由小到大排序而成的

字母都只有大寫英文字母，請找出所有出現過的字母由小到大排序後的樣子

想法

因為這題是給定兩元素之間的關係，然後求出排序後的樣子，所以可以想到用拓樸排序

透過比較相鄰兩字串之間第一個不同的字元，就可以找到一組關係式，根據這個關係我們可以在兩個元素之間建立一條邊，並且記錄下連到的元素入度大小

每次找到入度為 $0$ 的元素輸出，並且將下一個連接到的元素入度皆減 $1$

Code

// By Koios
#include<iostream>
using namespace std;
string pre, now;
int in[26], used[26], tot=0;
bool edge[26][26];
int main(){
	for(int i=0 ; i<26 ; i++){
		in[i] = 0;
		for(int j=0 ; j<26 ; j++){
			edge[i][j] = false;
		}
	}

	cin>>pre;
	for(int i=0 ; i<pre.size() ; i++){
		if(!used[pre[i]-'A']){
			used[pre[i]-'A']++;
			tot++;
		}
	}
	while(cin>>now && now!="#"){
		for(int i=0 ; i<now.size() ; i++){
			if(!used[now[i]-'A']){
				used[now[i]-'A']++;
				tot++;
			}
		}
		for(int i=0 ; i<pre.size() && i<now.size() ; i++){
			if(now[i] != pre[i]){
				if(!edge[pre[i]-'A'][now[i]-'A']){
					in[now[i]-'A']++;
					edge[pre[i]-'A'][now[i]-'A']=true;
				}
				break;
			}
		}
		pre=now;
	}

	for(int i=0 ; i<tot ; i++){
		for(int j=0 ; j<26 ; j++){
			if(in[j] == 0 && used[j]){
				in[j]--;
				cout<<(char)(j+'A');
				for(int k=0 ; k<26 ; k++){
					if(j==k) continue;
					if(edge[j][k]){
						in[k]--;
					}
				}
			}
		}
	}
	cout<<"\n";
	return 0;
}

時間複雜度分析

輸入時間複雜度為 $O(\sum{|now|})$

假設 $n = 26$

拓樸排序時間複雜度最差為 $O(n^3)$

總時間複雜度約為 $O(\sum{|now|} + n^3)$