dfs,10pts求调
查看原帖
dfs,10pts求调
654763
smallpeople楼主2024/11/20 12:23
#include<bits/stdc++.h>
using namespace std;

int n,m;
int ans;
vector <int> p[300005];

int dfs(int u,int uu)
{
	int mx = 0,mcx = 0,sum = 0;
	for(int i = 0;i < p[u].size();i ++)
	{
		int v = p[u][i];
		if(v == uu)
		{
			sum ++;
			continue;
		}
		if(p[v].size() == 1 && p[v][0] == u)
		{
			sum ++;
			continue;
		}
		
		int x = dfs(v,u);
		if(x >= mx)
		{
			mcx = mx;
			mx = x;
		}
		else if(x > mcx)mcx = x;
	}
	ans = max(ans,mx + mcx + sum + 1 - (mx != 0) - (mcx != 0));
	//cout<<u<<' '<<mx<<' '<<mcx<<' '<<sum<<' ';
	//cout<<mx + sum + 1 - (mx != 0)  + (mcx != 0)<<'\n';
	return mx + sum + 1 - (mx != 0) + (mcx != 0);
}

int main()
{
	cin>>n>>m;
	for(int i = 1;i <= m;i ++)
	{
		int a,b;
		cin>>a>>b;
		p[a].push_back(b);
		p[b].push_back(a);
	}
	//cout<<'\n';
	dfs(1,0);
	
	cout<<ans<<'\n';
	return 0;
}
2024/11/20 12:23
加载中...