#include<bits/stdc++.h> using namespace std; #define MAXSIZE 22 set<int>G[MAXSIZE]; int n,now; bool visited[MAXSIZE]; int ans[MAXSIZE]; bool f; //标记结果环是否找到 void dfs(int i) //判断图是否连通的基本dfs { visited[i]=true; for(set<int>::iterator it=G[i].begin();it!=G[i].end();it++) { if(!visited[*it]) { dfs(*it); } } } void my_dfs(int i) { if(f) return ; visited[i]=true; now++; ans[now]=i; //把当前结点存到结果数组里面 if(now==n&&G[ans[now]].count(ans[1])) //遍历完所有的结点了,判断最后一个结点是否能到起始结点 { f=true; //找到一个序列就标记输出,后面的都不用继续了 printf("%d",ans[1]); for(int i=2;i<=now;i++) { printf(" %d",ans[i]); } return ; } bool last=false; //判断没有访问过的结点有没有能到达起始结点的 for(int j=1;j<=n;j++) { if(!visited[j]&&G[j].count(ans[1])) { last=true; break; } } if(!last) return ; for(set<int>::iterator it=G[i].begin();it!=G[i].end();it++) { int t=(*it); //cout<<t<<" "<<endl; if(!visited[t]) { my_dfs(t); visited[t]=false; //dfs回退,将该结点从结果环中删除,找另外的环 now--; } } } bool Find_List() { for(int j=1;j<=n;j++) visited[j]=false; dfs(1); //先判断一下图是否连通 for(int j=1;j<=n;j++) { if(!visited[j]) return false;//图根本不连通,直接就结束了 } for(int i=1;i<=n;i++) //从最小的结点开始找环,让每个结点都为起始结点 { for(int j=1;j<=n;j++) visited[j]=false; now=0; my_dfs(i); if(f) return true; } return false; } int main() { scanf("%d",&n); char c; f=false; for(int i=1;i<=n;i++) //读入图到set中 { for(int j=1;j<=n;j++) { cin>>c; if(c=='W') G[i].insert(j); else if(c=='L') G[j].insert(i); } } if(!Find_List()) printf("No Solution"); return 0; } /* 5 //模拟一个不连通的图 -DDDD D-DWL DD-DW DDW-D DDDD- */
我这个说得有点啰嗦,可以参考下面这篇博客
https://blog.csdn.net/Morzker/article/details/102537956
1.写代码的时候模拟dfs的过程,想着怎么改进代码能到达想要的效果
2.想想办法对超时的dfs进行剪枝,有时候到达一个结点后没必要再递归下去了,递归是很费时的,对于特殊图(不连通)也可以单独处理
3.涉及序列最小时,都尽量在最开始就对结点排序,这样遍历过程中找到一个符合要求的即可直接输出并结束程序