UVa 539 The Settlers of Catan

题目描述题目要求在一个无向图中找出最长路径边不重复节点可重复。图中节点的度数不超过333节点数n≤25n \le 25n≤25边数m≤25m \le 25m≤25。输出最长路径的边数即路径长度。输入格式输入包含多个测试用例。每个测试用例的第一行包含两个整数nnn和mmm2≤n≤252 \le n \le 252≤n≤251≤m≤251 \le m \le 251≤m≤25。接下来mmm行每行两个整数uuu和vvv表示一条无向边。输入以0 0结束。输出格式对于每个测试用例输出一行一个整数表示最长路径的边数。样例输入3 2 0 1 1 2 15 16 0 2 1 2 2 3 3 4 3 5 4 6 5 7 6 8 7 8 7 9 8 10 9 11 10 12 11 12 10 13 12 14 0 0输出2 12题目分析本题的核心是在无向图中搜索最长路径边不可重复节点可重复。由于m≤25m \le 25m≤25可以直接使用深度优先搜索DFS\texttt{DFS}DFS枚举所有路径。搜索策略从每个节点出发进行DFS\texttt{DFS}DFS记录当前路径长度。使用visited[u][v]\textit{visited}[u][v]visited[u][v]标记边是否已被使用无向边双向标记。每当到达一个节点更新最大长度。递归搜索所有相邻的未使用边。剪枝由于度数≤3\le 3≤3搜索分支有限无需额外剪枝。复杂度分析最坏情况下完全图K25K_{25}K25​的边数为300300300但本题m≤25m \le 25m≤25且度数≤3\le 3≤3搜索空间有限。代码实现// The Settlers of Catan// UVa ID: 539// Verdict: Accepted// Submission Date:// UVa Run Time: s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAX_V30;intn,m,maxLength0,visited[MAX_V][MAX_V],connected[MAX_V][MAX_V];voiddfs(intu,intlength){maxLengthmax(maxLength,length);for(intv0;vn;v)if(connected[u][v]!visited[u][v]!visited[v][u]){visited[u][v]visited[v][u]1;dfs(v,length1);visited[u][v]visited[v][u]0;}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intfrom,to;while(cinnm,n0){memset(connected,0,sizeof(connected));for(inti1;im;i){cinfromto;connected[from][to]connected[to][from]1;}maxLength0;for(inti0;in;i){memset(visited,0,sizeof(visited));dfs(i,0);}coutmaxLength\n;}return0;}