树的深度题解
时间限制：0.2s 空间：32M
题目描述：
给你一棵以 1 为根的树，求树的深度，如下的树深为 5。
输入格式：
第一行输入一个整数 n，表示树的总点数。(1≤n≤1000)
第二行输入 n−1 个数，第 i 个数表示 i+1 的父节点标号
输出格式：
输出一个整数表示树的深度（根节点的深度为1）
样例输入：
10 8 4 8 10 1 1 1 3 8
样例输出：
5
题目分析：
树的深度指树的层数，高度，而与树的任意节点（除根节点）相连的边只有两种：
连接子节点或父节点。
所以就诞生了两种写法：
一，判断父节点
在DFS中定义三个参数：代表位置的id，代表父节点的dad和代表高度的sum。
如果tree(统计树节点的动态数组)[id][i]的位置（也就是与现在结点以边相连的另一节点）
不是父亲结点，那么继续往下深搜，tree[id][i]变为现在位置，父节点变为刚遍历完的节点，
高度加一。最后用mx(表示高度最大值）比较，完成！！
思路代码（DFS核心）：
void dfs(int id,int dad,int sum) {
for(int i=0;i<x[id].size();i++)
if(x[id][i]!=dad)dfs(x[id][i],id,sum+1);
if(sum>mx)mx=sum;
}
二，标记数组vis：
只要定义id和sum两个参数，额外定义一个标记数组vis，判断：如果此位置未被走过，标记；
思路代码：
void dfs(int id, int sum){
if (id == v){
printf("%d", sum);
return;
}
for (auto it : tree[id])
if (!vis[it]){
vis[it] = 1;
dfs(it, Dcnt + 1);
}
}
这里再把邻接表的输入说一下：
有向图：
cin>>n;
for(int i=2;i<=n;i++){
int sum;
cin>>sum;
x[sum].push_back(i);
}
无向图：
cin>>n;
for(int i=2;i<=n;i++){
int sum;
cin>>sum;
x[i].push_back(sum);
x[sum].push_back(i);
}