/*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 wouldexpect if the characters were ordered the same way as in the English alphabet. Thecollector tried to use the index to determine the ordering of characters (i.e., thecollating sequence) of the strange alphabet, then gave up with frustration at thetedium 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 particularcollating 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 allletters 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 XWYZXZXYZXWYWWX# 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#输出 ：AAAA# 输出 ：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;}

评论