算法竞赛模板

链接：https://ac.nowcoder.com/acm/contest/81600/H
来源：牛客网
#树
#DFS
There is an undirected graph where each vertex has a unique weight $ai$.

Initially, a chess piece is placed on a vertex. In each move, the piece moves to the adjacent vertex with the smallest weight. If all adjacent vertices have weights greater than the current vertex, the movement stops immediately.

You can freely assign weights $ai$ to the vertices (ensuring they are all unique) and choose the initial position of the chess piece. Your goal is to maximize the number of vertices visited by the chess piece.

1≤n≤40,1≤m≤(n(n+1)/2​),1≤u,v≤n.

题意：在一个无向图上选择一个顶点开始向相邻节点中权值最小的节点移动，可以自由赋权值，求最多的访问节点数目。

数据范围很小，可以考虑暴力DFS，从1~n个节点分别跑n遍DFS，至于权值可以先选出路径后再赋值。

但是如果一个节点有多个相邻节点，如果选择了其中一个节点，由于只能选择一个权值最小的节点，与它属于同个父亲的节点都无法访问,标记和回溯时要同时把周围的节点带上。

#include <bits/stdc++.h>
using namespace std;

int vis[50];
int ans = 0;
int n, m;
vector<vector<int>> adj(41);
int tmp;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    auto dfs = [&](auto& self, int p,int dep) -> void {
        ans = max(ans, dep);
        for (auto i : adj[p]) {
            if (vis[i]) continue;
            for (auto j : adj[p]) {
                if(vis[j]) continue;
                vis[j] = p+114514;
            }
            self(self, i,dep+1);
            for(auto j : adj[p]) {
                if(vis[j] == p+114514) vis[j] = 0;
            }
        }
    };
    for (int i = 1; i <= n; i++) {
        vis[i] = 1;
        dfs(dfs, i, 1);
        vis[i] = 0;
    }
    cout << ans << "\n";
    return 0;
}