牛客多校2024第五场

H 入

题意概括

无向图，任选一点开始走，若走到一点 $i$ 时，就把 $i$ 点的所有邻居都ban掉，问最多走几个点

思路

点数较少，可以暴力搜索
但是要注意的是，用邻接表存图的时候，回溯的时候可能会把不该重置的标记也重置了
什么意思呢？看这个图。
其实也可以不管这个，直接记录访问的次数，起点肯定多访问一次，也就不会在不该置为0的时候置0了

不记录次数的法一

#include <bits/stdc++.h>
#define endl '\n'
//#define int long long
using lli = long long;
using ull = unsigned long long;
typedef std::pair<int, int> pair;
typedef std::unordered_map<int, int> intmap;
typedef std::unordered_map<char, int> charmap;
std::vector<int> g[45];
bool vis[45] = {0};
int ans = 0;
 int n = 0, m = 0, u = 0, v = 0;
void dfs(int start, int cnt)
{   
    vis[start] = 1;
    for (auto x : g[start])
    {
        std::bitset<45> cur;
        if (vis[x]) continue;
        for (auto y : g[start])
        {
            if (y != x && !vis[y])
            {
                vis[y] = 1;
                cur[y] = 1;
            }
        }
        dfs(x, cnt + 1);
        for (auto y : g[start])
        {
            if (y != x && cur[y] == 1)
            {
                vis[y] = 0;
                cur[y] = 0;
            }
        }
    }
    ans = std::max(ans, cnt);
    vis[start] = 0;
}

void solve()
{
    int n = 0, m = 0, u = 0, v = 0;
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        g[i].clear();
    }
    for (int i = 1; i <= m; i++)
    {
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
    {
        dfs(i, 1);
    }
    std::cout << ans << endl;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 1; 
    //std::cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}

记录次数的法二

#include <bits/stdc++.h>
#define endl '\n'
//#define int long long
using lli = long long;
using ull = unsigned long long;
typedef std::pair<int, int> pair;
typedef std::unordered_map<int, int> intmap;
typedef std::unordered_map<char, int> charmap;
std::vector<int> g[45];
int vis[45] = {0};
int ans = 0;
int n = 0, m = 0, u = 0, v = 0;
void dfs(int start, int cnt)
{   
    for (int x : g[start])
    {
        if (vis[x]) continue;
        for (int y : g[start]) vis[y]++;
        dfs(x, cnt + 1);
        for (int y : g[start]) vis[y]--;
    }
    ans = std::max(ans, cnt);
}

void solve()
{
    int n = 0, m = 0, u = 0, v = 0;
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        g[i].clear();
    }
    for (int i = 1; i <= m; i++)
    {
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
    {
        vis[i]++;
        dfs(i, 1);
        vis[i]--;
    }
    std::cout << ans << endl;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 1; 
    //std::cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}