UVa 677 All Walks of Length n from the First Node

题目描述给定一个无向图节点数m≤10m \le 10m≤10要求输出从第111个节点出发、长度为nnn的所有不同节点序列即路径上的节点可以重复但代码中使用了used数组禁止重复访问因此实际要求是节点不重复的简单路径。输出按字典序排列每个序列用括号和逗号分隔。若不存在则输出no walk of length n。每个测试用例以-9999分隔。输入格式输入包含多个测试用例。每个测试用例第一行为节点数mmm和路径长度nnn。接下来mmm行是邻接矩阵000或111。测试用例之间由单独一行-9999分隔。输出格式对于每个测试用例输出所有满足条件的路径从节点111开始长度nnn节点不重复按字典序排列。若没有则输出no walk of length n。每组输出之间用空行分隔。样例输入5 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 -9999 5 3 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0输出(1,2,3) (1,4,3) (1,4,5) (1,2,3,4) (1,2,3,5) (1,4,3,2) (1,4,3,5) (1,4,5,3)题目分析本题要求在无向图中找出所有从节点111出发、长度为nnn、节点不重复的路径并按字典序输出。由于节点数最多101010路径长度nnn未给出上限但节点不重复意味着路径最长不超过mmm所以nnn必定小于等于mmm否则无解。使用深度优先搜索DFS\texttt{DFS}DFS枚举所有可能的路径并在搜索过程中按节点编号升序尝试以保证输出字典序。解题思路读入节点数nodes和路径长度walks注意代码中将walks加111以表示路径中的节点数因为长度nnn的路径包含n1n1n1个节点。构建邻接矩阵linked[i][j]。初始化selected[0] 1标记节点111已访问。执行DFS\texttt{DFS}DFS若当前深度depth等于路径长度即已选walks个节点则输出路径并计数。否则按节点编号从222到nodes升序遍历若该节点未访问且与当前节点相邻则选择该节点标记访问递归回溯取消标记。若最终solutions 0输出no walk of length n。注意输入中的-9999是分隔符但代码中直接读取solutions变量实际上代码中在读取邻接矩阵后cin solutions;但这solutions其实是输入的-9999从代码看solutions被用作计数器但读入的solutions其实是分隔符-9999但代码中将其赋给solutions覆盖了计数器导致错误实际上代码中cin solutions;读入的是分隔符但solutions随后被重置为000所以不影响。但更好的做法是用一个临时变量读取分隔符。复杂度分析最多节点101010路径长度≤10\le 10≤10枚举所有排列O(m!)O(m!)O(m!)但10!3.6×10610! 3.6 \times 10^610!3.6×106剪枝后更少完全可行。代码实现// All Walks of Length n from the First Node// UVa ID: 677// Verdict: Accepted// Submission Date: 2017-05-29// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intnodes,walks,solutions;intlinked[20][20],used[20],selected[20];voiddfs(intdepth){if(depthwalks){solutions;cout(1;for(inti1;iwalks;i)cout,selected[i];cout)\n;}else{for(inti2;inodes;i)if(!used[i]linked[selected[depth-1]][i]){used[i]1;selected[depth]i;dfs(depth1);used[i]0;}}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;while(cinnodeswalks){if(cases0)cout\n;for(inti1;inodes;i)for(intj1;jnodes;j)cinlinked[i][j];intseparator;cinseparator;// 读取 -9999memset(used,0,sizeof(used));solutions0,selected[0]1,used[1]1,walks1;dfs(1);if(solutions0)coutno walk of length (walks-1)\n;}return0;}总结本题通过深度优先搜索枚举所有从节点111出发的无重复节点路径并按升序尝试节点编号以保证字典序输出。关键点包括正确理解路径长度与节点数的关系。使用used数组避免节点重复。处理输入中的分隔符-9999。若不存在路径输出特定信息。