lit. original title points the way
original problem solving guide
Ex:For those of you who don't know what DFS is, take a look at this text (taken from OIwiki):
The most notable feature of DFS is itsRecursively calling itselfThe DFS is also similar to BFS in that it access-marks the points it accesses. Also similar to BFS, DFS marks the points it visits with access tags and skips tagged points when traversing the graph to ensure that theOnly one visit per pointThe function that meets the above two rules is a generalized DFS. A function that satisfies these two rules is a DFS in the broadest sense.
Specifically, the DFS is roughly structured as follows:
DFS(v) // v can be a vertex in the graph or an abstraction such as a dp state, etc.
Place an access marker on v
for u in v's neighboring nodes
if u is not access-marked then
DFS(u)
end
end
end
See here for details
Very simple binary tree traversal problem, still solved with dfs (depth-first search) like last time.
See the data range, up to a maximum of\(10^6\) You can leave it on.long long , each node is traversed only once and the time complexity is\(O(n)\)
Next on the code:
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int L[N],R[N],Max=-1;//L[u] denotes the left child node of u, R[u] denotes the right child node of U, Max is the max depth
void dfs(int u,int dep){//dep is the depth of current node
if(!L[u]&&!R[u]){//Minimal sub-problem (current node has no left and right child nodes)
Max=max(dep,Max);//beatdown to compare depths
return;
}
dfs(L[u],dep+1).
dfs(R[u],dep+1).
}
int main(){
cin>> ngt;
cin>>n;
for(int i=1;i<=n;i++){
cin>>L[i]>>R[i];//input
}
dfs(1,1);
cout<<Max;//output
return 0; }
}