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;
}
