无向图-已知根节点求高度

 

深搜板子题，无向图，加边加两个，dfs输入两个参数变量，一个是当前深搜节点，另一个是父节点（避免重复搜索父节点），恢复现场

///首先完成数组模拟邻接表#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 10010;
int ha[N],e[2*N],nx[2*N],idx;//数组模拟邻接表
bool vis[N];//标记数组int n,m;
int ans=0;
int res=0;void add(int a,int b){e[idx]=b;nx[idx]=ha[a];ha[a]=idx;idx++;
}
void dfs(int n,int fa){//进行遍历for(int i = ha[n]; i !=-1; i=nx[i]){int j = e[i];if(j==fa)continue;if(!vis[j]){//printf("j=%d, ans=%d \n",j,ans);ans=ans+1;//加1vis[j]=1;//标记dfs(j,n);//下一层res=max(ans,res);//取最大值ans--;//恢复现场vis[j]=0;//恢复}}
}int main(){scanf("%d%d",&n,&m);int a,b;memset(ha,-1,sizeof(ha));for(int i = 1; i < n; i++){scanf("%d%d",&a,&b);add(a,b);add(b,a);}dfs(m,-1);vis[m]=1;printf("%d\n",res);return 0;
}