原题：洛谷P2959
不得不说这道题的图有点吓人，但实际上很多都没有用
通过题上说的“三岔路口”（对于每一个节点有三条连接，其中一条连接父节点，另外两条连接子节点）和数据，可以那些乱七八糟的路和牧场看成是一棵二叉树，又因为 “对任意一个节点来说，只有一条从节点1开始的路径可以到达” ，所以可以把1作为根节点。从而将题目转化为求一棵以1为节点的二叉树的深度。
核心算法：DFS
注意：
1.根节点的深度在此题中应该为1（节点1的实际意义是一个要算入答案的一个牧场）
2.有n个节点，他们之间的连接数应该为n-1
#include<iostream> #include<cstdio> #include<cstring> #include<stack> #include<cmath> typedef long long ll; using namespace std; struct Node{ int id,l,r; Node(){ l=r=0; } }tr[1010];//保存二叉树 int p,dep[1010],ans=0;//个数，节点深度，答案（树的深度） void addedge(int i,int r,int l){ tr[i].id=i; tr[i].l=l; tr[i].r=r; }//编号为i的接点的左节点l，右节点r void Init() { scanf("%d",&p); int a,b,c; for(int i=1;i<p;i++){ scanf("%d%d%d",&a,&b,&c); addedge(a,b,c); } dep[1]=1;//注意初始化 } void DFS(int i){ if(tr[i].l){//如果左节点不为0 dep[tr[i].l]=dep[i]+1;//左节点的深度 ans=max(ans,dep[i]+1);//更新树的深度 DFS(tr[i].l);//接着左节点向下找 } if(tr[i].r){//同理 dep[tr[i].r]=dep[i]+1; ans=max(ans,dep[i]+1); DFS(tr[i].r); } } int main() { Init(); DFS(1); printf("%d",ans); return 0; }