题目描述
blablabla
样例
blablabla
参考链接: https://blog.csdn.net/yyt330507870/article/details/76684128
blablabla
时间复杂度分析:blablabla
C++ 代码
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<queue>
#define N 110000
#define INF 0x3f3f3f3f
using namespace std;
int n,m,a,b,vis[N],son[N],ans;
struct node
{
int d,w;
};//定义一个结构体来存储每个入度点以及对应边的权值
//比如边u->v,权值为w,node结构体存储的就是v以及w。
vector<node>v[N];
void dfs(int x);
int main()
{
//对于N非常大但是M很小的这种稀疏图来说,用邻接矩阵N*N是存不下的。邻接矩阵是将所有的点都存储下来了,然而
//对于稀疏图来说,有很多点是没有用到的,把这些点也存储下来的话就会很浪费空间。可以用邻接表来存储,这里借助vector来实现邻接表的操作。
//用邻接表存储时候,只存储有用的点,对于没有用的点不存储,实现空间的优化。
cin>>n;
for(int i=0; i<=n; i++)
v[i].clear();//将vecort数组清空
for(int i=1; i<=n-1; i++) //用vector存储邻接表
{
node nd;
scanf("%d%d",&a,&b);
nd.d=b,nd.w=1;//将入度的点和权值赋值给结构体
v[a].push_back(nd);//将每一个从a出发能直接到达的点都压到下标为a的vector数组中,以后遍历从a能到达的点就可以直接遍历v[a]
// nd.d=a,nd.w=c;//无向图的双向存边
// v[b].push_back(nd);
}
memset(vis,0,sizeof(vis));
memset(son,0,sizeof(son));
ans=INF;
dfs(1);
cout<<ans<<endl;
return 0;
}
void dfs(int x){
vis[x]=true;
int temp=0;//temp维护删除u结点后形成的最大子树结点数
vector<node> s=v[x];
for (int i = 0; i < s.size(); ++i) {
int v=s[i].d;
if(!vis[v]){
dfs(v);
son[x]=son[x]+son[v]+1;
temp=max(temp,son[v]+1);
}
}
temp=max(temp,n-son[x]-1);
if(temp<ans){
ans=temp;//ans维护删除某一结点形成最大子树结点数的最小值
}
}
输出 Wrong Answer