
From now onwards, Tubby = D and Tom = C. So D has to catch C and the first turn is of D. So, the very first thing is to create a tree from the given edge list. Here we create an adjacency list.
int min_time(int G_nodes, vector<int> G_from, vector<int> G_to , int D, int C){ vector<int> adj[G_nodes+1]; for(int i=0;i<G_nodes-1;i++){ adj[G_from[i]].push_back(G_to[i]); //Edges are undirected adj[G_to[i]].push_back(G_from[i]); } }
Now, we will apply DFS and create distance_d and distance_c arrays which denotes the distance of ith node from initial position of D and C respectively. This means, now we know the time D and C will take to reach any particular node from it’s starting position.
void dfs(int node, int p, int depth, vector<int> adj[], int dist[]){ dist[node] = depth; for(int i:adj[node]){ if (i == p) continue; dfs(i,node,depth+1,adj,dist); } } int min_time(int G_nodes, vector<int> G_from, vector<int> G_to , int D, int C){ vector<int> adj[G_nodes+1]; for(int i=0;i<G_nodes-1;i++){ adj[G_from[i]].push_back(G_to[i]); //Edges are undirected adj[G_to[i]].push_back(G_from[i]); } int distance_d[G_nodes+1], distance_c[G_nodes+1]; dfs(D,D,0,adj,distance_d); dfs(C,C,0,adj,distance_c); }
If at a node, D reaches first, i.e., distance_d[node] <= distance_c[node]+1, than C will never go to such node (not optimal). Thus, when distance_d[node] > distance_c[node]+1, C can be pruned and the ans will be updated as ans = max(ans, distance_d[node] + distance_d[node] -1). Because when C is caught, it has made one step less than what D has made.
Note : Answer always exist, as tree does not contain cycles. For detail explanation, I will include a link to my youtube video below!
Complete Code :
void dfs(int node, int p, int depth, vector<int> adj[], int dist[]){ dist[node] = depth; for(int i:adj[node]){ if (i == p) continue; dfs(i,node,depth+1,adj,dist); } } int min_time(int G_nodes, vector<int> G_from, vector<int> G_to , int D, int C){ vector<int> adj[G_nodes+1]; for(int i=0;i<G_nodes-1;i++){ adj[G_from[i]].push_back(G_to[i]); //Edges are undirected adj[G_to[i]].push_back(G_from[i]); } int distance_d[G_nodes+1], distance_c[G_nodes+1]; dfs(D,D,0,adj,distance_d); dfs(C,C,0,adj,distance_c); int ans = 1; for(int i=1;i<=G_nodes;i++){ if (distance_d[i] > distance_c[i]+1){ ans = max(ans, distance_d[i]*2 -1); } } return ans; }