原题:
L3-015 球队“食物链”
时间限制1000 ms-------内存限制262144 kB---------代码长度限制8000 B---------判题程序Standard---------作者李文新（北京大学）
某国的足球联赛中有N支参赛球队，编号从1至N。联赛采用主客场双循环赛制，参赛球队两两之间在双方主场各赛一场。
联赛战罢，结果已经尘埃落定。此时，联赛主席突发奇想，希望从中找出一条包含所有球队的“食物链”，来说明联赛的精彩程度。“食物链”为一个1至N的排列{ T1 T2 ... TN }，满足：球队T1战胜过球队T2，球队T2战胜过球队T3，……，球队T(N-1)战胜过球队TN，球队TN战胜过球队T1。
现在主席请你从联赛结果中找出“食物链”。若存在多条“食物链”，请找出字典序最小的。
注：排列{ a1 a2 ...aN }在字典序上小于排列{ b1 b2 ... bN }，当且仅当存在整数K（1 <= K <= N），满足：aK < bK且对于任意小于K的正整数i，ai=bi。
输入格式：
输入第一行给出一个整数N（2 <= N <= 20），为参赛球队数。随后N行，每行N个字符，给出了NxN的联赛结果表，其中第i行第j列的字符为球队i在主场对阵球队j的比赛结果：“W”表示球队i战胜球队j，“L”表示球队i负于球队j，“D”表示两队打平，“-”表示无效（当i=j时）。输入中无多余空格。
输出格式：
按题目要求找到“食物链”T1 T2 ... TN，将这N个数依次输出在一行上，数字间以1个空格分隔，行的首尾不得有多余空格。若不存在“食物链”，输出“No Solution”。
输入样例1：
5 -LWDW W-LDW WW-LW DWW-W DDLW-
输出样例1：
1 3 5 4 2
输入样例2：
5 -WDDW D-DWL DD-DW DDW-D DDDD-
输出样例2：
No Solution
个人解题思路:
本题是图的深度优先搜索 ( DFS ) 的应用。把球队看成节点，如果球队胜过另一支球队，则它们存在一条有向边，由胜方指向败方。构图以后，找出图中的包含所有节点的回路即可。
不过虽然思路可能比较好想，但是题目本身还是有很多小陷阱。 第一是关于胜负的判断。两支球队存在边，可以是一方胜过一方，也可以是一方负给另一方，这个问题的判断好像涉及到测试点 3 。 第二是超时的问题。要尽可能减小查找时间。第一个优化点：因为图是一个回路，所以如果存在解的话，必然可以从节点一回到节点一。刚好题目又要求字典序最小，所以第一个节点必从节点一开始，节点一无解的话后面节点都不需要再找了。第二个优化点：是在搜索过程中，可以对后续节点进行判断，如果后续节点没有能回到第一个节点的，则不必再往下搜索了。源代码:
char arcs[30][30];//存胜负信息bool vis[30];//节点是否被访问int list[30];//路径int n;//总共多少支队伍int cnt;//计数
#includechar arcs[30][30];//存胜负信息bool vis[30];//节点是否被访问int list[30];//路径int n;//总共多少支队伍int cnt;//计数//深度优先搜索bool DFS(int line){ int tag = 0; if(!vis[line]) { vis[line]=true; list[cnt++] = line; if(cnt == n ) { //判读最后一个节点是否能到达第一个节点 if(arcs[line][list[0]] == 'W' || arcs[list[0]][line] == 'L') { return true; } else { vis[line]=false; cnt--; return false; } } for(int j = 0; j < n;j++) { //查找后续节点是否有能到达第一个节点的节点，没有则不再寻找，如果有则继续 if(!vis[j] && (arcs[j][list[0]] == 'W' || arcs[list[0]][j] == 'L')) { tag = 1; break; } } if(tag == 0) { vis[line] = false; cnt--; return false; } for(int j = 0; j < n;j++) { //如果有节点未被访问过且输给当前节点 if( !vis[j] && ( arcs[line][j] == 'W' || arcs[j][line] == 'L' ) ) { if(DFS(j)) { return true; } } } vis[line] = false; cnt--; } return false;}int main(int argc, const char * argv[]) { int pass; while (scanf("%d",&n) != EOF) { cnt = 0; pass = 0; while (cnt < n) { scanf("%s",&arcs[cnt]); cnt++; } cnt = 0;//计数路中已有的节点 vis[0] = true; list[cnt++]= 0; for(int j = 0; j < n;j++) { if(arcs[0][j] == 'W' || arcs[j][0] == 'L') { if (DFS(j)) { pass = 1; break; } } } if(pass == 1) { for(int i = 0 ; i < n ; i ++) { printf("%d",list[i] + 1); if(i + 1 < n)printf(" "); } printf("\n"); } else { printf("No Solution\n"); } } return 0;}