UVa 200 Rare Order：拓扑排序

UVa 200 Rare Order：拓扑排序2014-07-25

200 - Rare Order

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=136

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

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

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

完整代码：

/*0.016s*/#include<bits/stdc++.h>using namespace std;list<int> 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<int>::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;}