题目描述
使用vector动态数组构建邻接表
dfs算法主体部分由递归+循环组成,递归保证算法不断的向下搜索,循环保证回溯时可以找到分支节点。在dfs中每一条路径都可以看成一个结果。
从一条路径遍历到底,但在遍历的过程中递归会记录你所遍历过每一个节点,
当一条路径遍历结束我们就可以获得该条路径的结果(路径的长度或其他题目需要去计算的),
此后将不断回溯,回溯到有分支(循环控制分支)的节点时,将再次遍历一条路径,不断重复此操作直到遍历完所有节点
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<vector>
using namespace std;
const int N=1e5+10;
vector<int>v[N];
bool status[N]; // 修改为布尔类型并初始化
int ans=N; // 初始化为一个较大的值
int n;
void add(int a,int b)
{
v[a].push_back(b);
v[b].push_back(a);
}
int dfs(int u)
{
status[u]=true; // 标记节点为已访问
int res=0,sum=0; //
for(int i=0;i<v[u].size();i++)
{
if(!status[v[u][i]]) // 如果邻接节点未被访问过
{
int s=dfs(v[u][i]); // 递归访问邻接节点
res=max(s,res); // 更新res
sum+=s; // 更新sum
}
}
res=max(res,n-sum-1); // 考虑当前节点外的节点数目
ans=min(ans,res); // 更新ans
return sum+1; //当前连通块要+1,sum得到的是子树和
}
int main()
{
cin>>n;
for(int i=0;i<n-1;i++) // 假设输入的是树形结构,边数应为节点数减一
{
int a,b;
cin>>a>>b;
add(a,b);
}
dfs(1);
cout<<ans;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla