UVa 200 Rare Order (拓扑排序) - c++编程基础

题意：给一列单词，这些单词是按一种未知的字典顺序排列的，要求输出这些字母的顺序。

思路：很明显，拓扑排序。

注意最后要多输出一个换行，否则会WA！

完整代码：

/*0.016s*/  
  
#include  
using namespace std;  
  
list l[27];  
char last[25], now[25];  
bool has[27], vis[27];  
int ans[27], cnt;  
  
void dfs(int i)  
{  
    vis[i] = true;  
    if (l[i].size())  
        for (list::iterator iter = l[i].begin(); iter != l[i].end(); ++iter)  
            if (!vis[*iter]) dfs(*iter);  
    ans[cnt++] = i;  
}  
  
int main()  
{  
    int len, i;  
    gets(last);  
    has[last[0] & 31] = true;  
    while (gets(now), now[0] != '#')  
    {  
        len = min(strlen(last), strlen(now));  
        for (i = 0; i < len; ++i)  
        {  
            if (last[i] != now[i])  
            {  
                has[last[i] & 31] = has[now[i] & 31] = true;  
                l[last[i] & 31].push_back(now[i] & 31);  
                break;  
            }  
        }  
        memcpy(last, now, sizeof(now));  
    }  
    for (i = 1; i < 27; ++i)  
        if (has[i] && !vis[i]) dfs(i);  
    for (i = cnt - 1; i >




= 0; --i)  
        putchar(ans[i] + 'A' - 1);  
    putchar(10);///尝试加了个换行，就AC了，果然是我太年轻。。。  
    return 0;  
}