dfs
关于dfs,我想说这些:
要明确我们进行dfs的目的是什么,是遍历节点并将他们输出,或搜索路径,亦或者统计节点的个数,还是在利用上面的几种操作的结果来进行其他操作。如果是第一种的话,dfs是没有返回值的,如果是第二种的话,输入参数需要有路径数组,如果是第三种的话,返回值是int整型。如果是最后一种的话,我们就要想清楚其中的逻辑,然后套用上述三种情况的模板即可。
关于这道题目
1.树是无环连通图
2.由于本题是无向树,也就是说从树的任意一个节点出发都能够到达其他节点
3.树的每一个节点的子树都是不互相交的集合
4.剩下的我在代码里解释了
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010,M=2*N;
int n;
int e[M],ne[M],idx,h[N],ss[N],ans=N;//h里存放的是树的节点
//树是无环连通图
//由于本题是无环树,也就是说从树的任意一个节点出发都能够到达其他节点
void add(int x,int y){//用邻接表来存储树或者图
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}
/*
要明确我们进行dfs的目的是什么,是遍历节点并将他们输出,或搜索路径,亦或者统计
节点的个数,还是在利用上面的几种操作的结果来进行其他操作。如果是第一种的话,
dfs是没有返回值的,如果是第二种的话,输入参数需要有路径数组,如果是第三种的话,
返回值是int整型。如果是最后一种的话,我们就要想清楚其中的逻辑,然后套用上述三种情况
的模板即可。
*/
int dfs(int x){
ss[x]=1;//标志着这个数据已经被访问过
//深度优先搜索呢,就是寻找它的一个连通节点,然后一条路走到黑,最后回溯
//回溯的话,我们交给递归完成
int i=h[x],sum=0,res=0;
while(i!=-1){
int j=e[i];//j是节点x的连通节点
if(!ss[j]){
//问题来了,怎么计算连通块中节点的数目
//利用dfs统计它子树节点个数
int t=dfs(j);
res=max(res,t);
sum+=t;//对于节点x,它的各个子树又是互不相交的集合,所以
//我们通过统计它的各个子树中节点的数量,并于res相比较,就可以得到
//它子树中的最大连通块,res存放的是子树种节点个数的最大值
}
i=ne[i];
}
//res存放的仅仅是节点x的的最大子树,还有它的父节点部分的连通块中节点的个数
res=max(res,n-sum-1);
ans=min(res,ans);
return sum+1;
}
int main(){
memset(h,-1,sizeof h);
scanf("%d",&n);
for(int i=1;i<n;++i){
int x,y;
scanf("%d %d",&x,&y);
add(x,y);
add(y,x);
}
dfs(n-2);//所以从那个节点开始遍历都可以
cout<<ans;
return 0;
}