解题思路

这道题要求我们在一个无向图中找到不重复经过任何边的最长路径。由于节点可以重复访问，但边不能重复使用，我们需要使用 DFS（深度优先搜索） + 回溯 的方法来遍历所有可能的路径，并记录最长的那一条。

关键点

1. 图的存储：使用邻接表（vector<vector<pair<int, int>>>）存储图，其中 pair<int, int> 存储邻接节点和边的编号（用于标记是否访问过）。
2. DFS 遍历：
   • 从每个节点出发进行 DFS，尝试所有可能的路径。
   • 用 visited_edge 数组标记已经访问过的边，防止重复使用。
   • 在 DFS 过程中维护当前路径长度 current_length，并更新全局最大值 max_length。
3. 回溯：
   • 在递归返回时，恢复边的访问状态（visited_edge），以便其他路径可以正常遍历。

优化

• 由于节点度数 ≤ 3，DFS 的时间复杂度不会太高（最坏情况 $O(3^{25})$，但实际剪枝后可行）。
• 不需要考虑所有起点，因为无向图的最长路径可能从任意节点开始，所以必须尝试所有可能的起点。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int max_length; // 全局变量，记录最长路径长度

void dfs(int node, vector<vector<pair<int, int> > > &graph, vector<bool> &visited_edge, int current_length) {
    max_length = max(max_length, current_length); // 更新最大值
    for (vector<pair<int, int> >::iterator it = graph[node].begin(); it != graph[node].end(); ++it) {
        int next_node = it->first;
        int edge_id = it->second;
        if (!visited_edge[edge_id]) {
            visited_edge[edge_id] = true; // 标记边已访问
            dfs(next_node, graph, visited_edge, current_length + 1);
            visited_edge[edge_id] = false; // 回溯，恢复状态
        }
    }
}

int main() {
    int n, m;
    while (cin >> n >> m, n || m) {
        vector<vector<pair<int, int> > > graph(n); // 邻接表存储图
        vector<bool> visited_edge(m, false);     // 标记边是否访问过

        for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(make_pair(v, i)); // 无向图，双向存储
            graph[v].push_back(make_pair(u, i));
        }

        max_length = 0;
        for (int i = 0; i < n; ++i) {
            dfs(i, graph, visited_edge, 0); // 从每个节点出发尝试DFS
        }
        cout << max_length << endl;
    }
    return 0;
}