题目描述

对于每个点，已知其邻居的数目。给出序列要求：邻居的数目必须得增长。求这样序列的最大长度

Input

6 9 
0 1 
0 4 
1 2 
1 3 
1 4 
1 5 
2 5 
3 4 
4 5

Output

4 

DFS+剪枝

对一个点的所有邻居进行遍历，当邻居节点的邻居数目大于当前点的邻居数目时，进行dfs。然而如果对每个点都进行dfs的话，会TLE，有一步的剪枝。由于，这样一种情况的存在，当之后访问到之前访问过的节点时，可以直接维护最值。

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>
typedef long long ll;
ll n,m;
const int maxn=3e5+5;
ll vis[maxn];
using namespace std;
vector<ll>side[maxn];
ll dfs(ll x)
{
    if(!vis[x])
    {
        vis[x]=1;
        for(ll i=0;i<side[x].size();i++)
        {
            ll dy=side[x][i];
            if(side[dy].size()>side[x].size())
                vis[x]=max(vis[x],dfs(dy)+1); 
        }
    }
    return vis[x];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        ll x,y;
        cin>>x>>y;
        side[x].push_back(y);
        side[y].push_back(x); 
    }
    ll ans=0;
    for(int i=0;i<n;i++)
    {    if(!vis[i])
        ans=max(ans,dfs(i));
    }
    cout<<ans;

}