如下三个坑点：
1、所给的图非对称，因为每个队打了两场比赛，每一场分别记输赢。所以每行数据都要做处理。
2、要求食物链的字典序最小，而且该食物链是从1到n的排列，因此只要有环，头一个一定从1开始是字典序最小的状况，只需要从1开始DFS即可。
3、剪枝：不剪枝T一个点。在DFS中把经过的点标记，若未标记的点集中不存在与1连通的点，则不可能构成环状结构，直接return false。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include<iostream> #include<stack> #include<queue> using namespace std; int n; char arr[25][25]; deque<int> st; bool visited[25]; bool dfs(int curNode,int visitedNodeCnt){ if(visited[curNode]){ if(visitedNodeCnt==n+1&&curNode==1)return true; else return false; } bool flag=false; for(int i=1;i<=n;i++){ if(!visited[i]&&(arr[i][1]=='W'||arr[1][i]=='L'))flag=true; } if(!flag)return false; visited[curNode]=true; for(int i=1;i<=n;i++){ if(i==curNode)continue; if(arr[curNode][i]=='W'||arr[i][curNode]=='L'){ if(dfs(i,visitedNodeCnt+1)){ st.push_back(i); return true; } } } visited[curNode]=false; return false; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%s",arr[i]+1); bool flag=dfs(1,1); if(!flag)printf("No Solution\n"); else{ printf("%d",st.front()); st.pop_front(); while(!st.empty()){ printf(" %d",st.back()); st.pop_back(); } } } |