/*
Rare Order
Problem description
A rare book collector recently discovered a book written in an unfamiliar language
that used the same characters as the English language. The book contained a short
index, but the ordering of the items in the index was different from what one would
expect if the characters were ordered the same way as in the English alphabet. The
collector tried to use the index to determine the ordering of characters (i.e., the
collating sequence) of the strange alphabet, then gave up with frustration at the
tedium of the task.
You are to write a program to complete the collector's work. In particular, your
program will take a set of strings that has been sorted according to a particular
collating sequence and determine what that sequence is.
Input
The input consists of several blocks. Each block is an ordered list of strings of
uppercase letters, one string per line. Each string contains at most 20 characters.
The end of the list is signalled by a line dio is the single character `#'. Not all
letters are necessarily used, but the list will imply a complete ordering among
those letters that are used. End of file marks end of last block.
Output
Your output should be a single line containing uppercase letters in the order that
specifies the collating sequence used to produce the input data file.
Sample Input
XWY
ZX
ZXY
ZXW
YWWX
#
Sample Output
XZYW
**/
///// 题目没看懂的，看下下面的，开始我也没懂
/*
每对字母之间存在着单向的传递关系，比如样例
XWY
ZX
ZXY
ZXW
YWWX
#
从1，2行可知Z>X,从3，4行可知W>Y,从4，5行可知Y>Z,所以所有字母的传递关系是W>Y>Z>X,输出XZYW.
从相邻两行有可能得到一对字母之间的传递关系，比较方法是字典排序法：
从前往后扫描两行，如果出现的对应字母不同，则可以确定这对字母的先后关系。
注意这种数据：
AAAAA
#
输出 ：A
A
A
A
#
输出 ：A (这种数据害我WA了几次)
*/
////////// 以前没做过拓扑排序，下面的主要是拓扑排序
///////// 别人同样的算法 203 ms, 我的 543ms 郁郁, 代码全部公开,仅供学习 !!!!!
#include <iostream>
#include <list>
using namespace std;
int myCmp(const char *str1, const char *str2){
int i;
for(i=0; str1[i]&&str2[i]&&str1[i]==str2[i]; i++)
;
if(!str1[i] || !str2[i])
return -1;
return i;
}
void getResult(int pb[][26],bool appear[]){
int i,k,a[26]={0};
list<int> node;
for(k=0; k<26; k++){
if(!appear[k])
continue;
node.push_back(k);
for(i=0; i<26; i++)
if(pb[i][k])
a[k]++;
}
list<int>::iterator it,itp;
for(it=node.begin(); it!=node.end(); ){
if(a[*it]==0){
cout<<(char)(*it+'A');
for(itp=node.begin(); itp!=node.end(); itp++)
if(pb[*it][*itp])
a[*itp]--;
node.erase(it);
it=node.begin();
}
else
it++;
}
cout<<endl;
}
int main(){
int bAlpha[26][26]={0};
char szStr1[22],szStr2[22];
bool bFlag,bAppear[26]={false};
for(bFlag=false,szStr2[0]='\0'; cin>>szStr1;){
if(szStr1[0]=='#'){
if(!bFlag)
cout<<szStr2[0]<<endl;
else {
bFlag = false;
getResult(bAlpha,bAppear);
}
memset(bAlpha,0,sizeof(int)*26*26);
memset(bAppear,false,sizeof(bool)*26);
szStr2[0]='\0';
continue;
}
int i=myCmp(szStr1,szStr2);
if(i != -1){
bFlag = true;
bAlpha[szStr2[i]-'A'][szStr1[i]-'A'] = 1;
bAppear[szStr2[i]-'A'] = bAppear[szStr1[i]-'A'] = true;
}
strcpy(szStr2,szStr1);
}
return 0;
}
//////// 没用拓扑排序，根据 warshall 算法写的， 六百多 ms , 晕晕
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
typedef struct node{
int i,j;
node(int a=0,int b=0):i(a),j(b){}
}NODE;
int myCmp(const char *str1, const char *str2){
int i;
for(i=0; str1[i]&&str2[i]&&str1[i]==str2[i]; i++)
;
if(!str1[i] || !str2[i])
return -1;
return i;
}
void getK(int k,bool pb[][27]){
for(int i=0; i<26; i++){
if(pb[k][i]){
if(!pb[i][26])
getK(i,pb);
for(int j=0; j<26; j++)
if(pb[i][j])
pb[k][j] = true;
}
}
pb[k][26] = true;
}
void dealMeter(bool pb[][27],bool appear[]){
for(int k=0; k<26; k++){
if(!appear[k] || pb[k][26])
continue;
getK(k,pb);
}
}
bool myCmpSort(const NODE &a , const NODE &b){
return a.j < b.j;
}
void printResult(bool pb[][27],bool appear[]){
int nRlt[26],i;
for(i=0; i<26; i++){
nRlt[i] = appear[i] ? 1 : 0;
nRlt[i] += count(pb[i],pb[i]+26,true);
}
vector<NODE> p;
for(i=0; i<26; i++){
if(nRlt[i])
p.push_back(node(i,nRlt[i]));
}
sort(p.begin(),p.end(),myCmpSort);
for(i=0; i<p.size(); i++)
cout<<(char)(p[i].i+'A');
cout<<endl;
}
int main(){
bool bAlpha[26][27]={false},appear[26]={false};
char szStr1[22],szStr2[22];
bool flag;
for(flag=false,szStr2[0]='\0'; cin>>szStr1;){
if(szStr1[0]=='#'){
if(!flag)
cout<<szStr2[0]<<endl;
else {
flag = false;
dealMeter(bAlpha,appear);
printResult(bAlpha,appear);
}
memset(bAlpha,false,sizeof(bool)*26*27);
memset(appear,false,sizeof(bool)*26);
szStr2[0]='\0';
continue;
}
int i=myCmp(szStr1,szStr2);
if(i != -1){
flag = true;
bAlpha[szStr1[i]-'A'][szStr2[i]-'A'] = true;
appear[szStr2[i]-'A'] = appear[szStr1[i]-'A'] = true;
}
strcpy(szStr2,szStr1);
}
return 0;
}
评论