Maximum Distance with Blocked Edges from Vertex 0
Given N vertices numbered from 0 to N – 1. There are N – 1 bidirectional edges given where edges[i][0] and edges[i][1] are connected. Given q queries[][] representing which edge is blocked. For each query, we need to tell the maximum distance we can travel starting from vertex 0 remembering we can’t travel over the edge (connected by vertex query[i][0] and query[i][1]).
Examples:
Input: N = 5, Q = 2, Edge[][] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}}, query = {{0, 1}, {1, 4}}
Output: 1 2
Explanation: The structure looks like this:0
/ \
1 2
/ \
3 4Query 1: the edge connecting (0, 1) is blocked. Only 0 and 2 are reachable.
- For vertex 0, distance = 0.
- For vertex 2, distance = 1.
Maximum (vertex 0, vertex 1) = 1
Query 2: The edge connecting (1, 4) is blocked. Onlyvertex 0, 1, 2 and 3 are reachable.
- For vertex 0, distance = 0.
- For vertex 1, distance = 1.
- For vertex 2, distance = 1.
- For vertex 3, distance = 2.
A maximum distance of 2 => 0 -> 1 -> 3
Input: N = 3, Q = 1, Edge[][] = {{0, 1}, {0, 2}}, query[][] = {{0, 1}}
Output: 1
Explanation: Structure looks like:0
/ \
1 2
Approach: This can be solved with the following idea:
Using Euler’s idea, if we get at what time vertex enters into role and at what time it is excluded. We can easily fetch out, what is the maximum depth by remaining structure i.e. maximum distance we can travel.
Below are the steps involved:
- Create a adjancy matrix adj[][] of parents and children connected.
- Iterate in dfs function:
- Use in_time and out_time to store upto when each vertex was included.
- Also, add depth of each vertex in depth[] array.
- After iterating, store in pref and suff maximum depth.
- To answer the queries:
- Return max(pref[in_time[it[0]] – 1], suff[out_time[it[0]] + 1]) in ans.
- Return ans.
Below is the implementation of the code:
C++
// C++ code for the above approach: #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to iterate at each vertex // to know at what point vertex enters // and get out void dfs(vector< int > adj[], int u, int p, int depth[], int tour[], int in_time[], int out_time[], int & tick) { // When vertex enters tour[++tick] = depth[u]; in_time[u] = tick; // Iterate for that particular vertex for ( auto i : adj[u]) { // If it is not parent if (i != p) { // Increment in depth i.e. distance depth[i] = depth[u] + 1; // Iterate for child dfs(adj, i, u, depth, tour, in_time, out_time, tick); } } // When vertex leaves tour[++tick] = depth[u]; out_time[u] = tick; } vector< int > solve( int N, int Q, vector<vector< int > >& Edge, vector<vector< int > >& query) { // Intialise int N2 = 2 * N; vector< int > adj[N]; vector< int > ans; // To maintain distance for each vertex int depth[N] = { 0 }; int euler[N2]; // To maintain time of each vertex int in_time[N]; int out_time[N]; int tick = -1; int pref[N2]; int suff[N2]; // To create a adjancy matrix for ( auto it : Edge) { adj[it[0]].push_back(it[1]); adj[it[1]].push_back(it[0]); } // Start Iterating to maintain time dfs(adj, 0, -1, depth, euler, in_time, out_time, tick); pref[0] = euler[0]; suff[N2 - 1] = euler[N2 - 1]; // To add depth for each vertex to answer queries for ( int i = 1; i < N2; i++) { pref[i] = max(pref[i - 1], euler[i]); suff[N2 - i - 1] = max(suff[N2 - i], euler[N2 - i - 1]); } // Answering queries for ( auto it : query) { // To get parent and children if (depth[it[0]] < depth[it[1]]) swap(it[0], it[1]); // Add the maximum depth ans.push_back(max(pref[in_time[it[0]] - 1], suff[out_time[it[0]] + 1])); } return ans; } // Driver code int main() { // Input int N = 3; int Q = 1; vector<vector< int > > Edge = { { 0, 1 }, { 0, 2 } }; vector<vector< int > > query = { { 0, 1 } }; // Function call vector< int > ans = solve(N, Q, Edge, query); int i = 0; while (i < ans.size()) { cout << ans[i] << " "; i++; } return 0; } |
Java
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Main { static int tick = - 1 ; // Function to iterate at each vertex // to know at what point vertex enters // and get out static void dfs(List<Integer>[] adj, int u, int p, int [] depth, int [] tour, int [] in_time, int [] out_time) { // When the vertex enters tour[++tick] = depth[u]; in_time[u] = tick; // Iterate for that particular vertex for ( int i : adj[u]) { // If it is not the parent if (i != p) { // Increment in depth i.e. distance depth[i] = depth[u] + 1 ; // Iterate for the child dfs(adj, i, u, depth, tour, in_time, out_time); } } // When the vertex leaves tour[++tick] = depth[u]; out_time[u] = tick; } static List<Integer> solve( int N, int Q, List< int []> Edge, List< int []> query) { // Initialize int N2 = 2 * N; List<Integer>[] adj = new ArrayList[N]; for ( int i = 0 ; i < N; i++) { adj[i] = new ArrayList<>(); } List<Integer> ans = new ArrayList<>(); // To maintain distance for each vertex int [] depth = new int [N]; int [] euler = new int [N2]; // To maintain time of each vertex int [] in_time = new int [N]; int [] out_time = new int [N]; int [] pref = new int [N2]; int [] suff = new int [N2]; // To create an adjacency list for ( int [] it : Edge) { adj[it[ 0 ]].add(it[ 1 ]); adj[it[ 1 ]].add(it[ 0 ]); } // Start iterating to maintain time dfs(adj, 0 , - 1 , depth, euler, in_time, out_time); pref[ 0 ] = euler[ 0 ]; suff[N2 - 1 ] = euler[N2 - 1 ]; // To add depth for each vertex to answer queries for ( int i = 1 ; i < N2; i++) { pref[i] = Math.max(pref[i - 1 ], euler[i]); suff[N2 - i - 1 ] = Math.max(suff[N2 - i], euler[N2 - i - 1 ]); } // Answering queries for ( int [] it : query) { // To get parent and children if (depth[it[ 0 ]] < depth[it[ 1 ]]) { int temp = it[ 0 ]; it[ 0 ] = it[ 1 ]; it[ 1 ] = temp; } // Add the maximum depth ans.add(Math.max(pref[in_time[it[ 0 ]] - 1 ], suff[out_time[it[ 0 ]] + 1 ])); } return ans; } public static void main(String[] args) { // Input int N = 3 ; int Q = 1 ; List< int []> Edge = Arrays.asList( new int []{ 0 , 1 }, new int []{ 0 , 2 }); List< int []> query = Arrays.asList( new int []{ 0 , 1 }); // Function call List<Integer> ans = solve(N, Q, Edge, query); int i = 0 ; while (i < ans.size()) { System.out.print(ans.get(i) + " " ); i++; } } } |
Python3
def dfs(adj, u, p, depth, tour, in_time, out_time, tick): # When vertex enters tick[ 0 ] + = 1 tour[tick[ 0 ]] = depth[u] in_time[u] = tick[ 0 ] # Iterate for that particular vertex for i in adj[u]: # If it is not the parent if i ! = p: # Increment in depth, i.e., distance depth[i] = depth[u] + 1 # Iterate for the child dfs(adj, i, u, depth, tour, in_time, out_time, tick) # When vertex leaves tick[ 0 ] + = 1 tour[tick[ 0 ]] = depth[u] out_time[u] = tick[ 0 ] def solve(N, Q, Edge, query): # Initialize N2 = 2 * N adj = [[] for _ in range (N)] ans = [] # To maintain distance for each vertex depth = [ 0 ] * N euler = [ 0 ] * N2 # To maintain time of each vertex in_time = [ 0 ] * N out_time = [ 0 ] * N tick = [ - 1 ] pref = [ 0 ] * N2 suff = [ 0 ] * N2 # To create an adjacency list for it in Edge: adj[it[ 0 ]].append(it[ 1 ]) adj[it[ 1 ]].append(it[ 0 ]) # Start iterating to maintain time dfs(adj, 0 , - 1 , depth, euler, in_time, out_time, tick) pref[ 0 ] = euler[ 0 ] suff[N2 - 1 ] = euler[N2 - 1 ] # To add depth for each vertex to answer queries for i in range ( 1 , N2): pref[i] = max (pref[i - 1 ], euler[i]) suff[N2 - i - 1 ] = max (suff[N2 - i], euler[N2 - i - 1 ]) # Answering queries for it in query: # To get parent and children if depth[it[ 0 ]] < depth[it[ 1 ]]: it[ 0 ], it[ 1 ] = it[ 1 ], it[ 0 ] # Add the maximum depth ans.append( max (pref[in_time[it[ 0 ]] - 1 ], suff[out_time[it[ 0 ]] + 1 ])) return ans # Driver code if __name__ = = "__main__" : # Input N = 3 Q = 1 Edge = [[ 0 , 1 ], [ 0 , 2 ]] query = [[ 0 , 1 ]] # Function call ans = solve(N, Q, Edge, query) for a in ans: print (a, end = " " ) |
C#
using System; using System.Collections.Generic; class MainClass { static int tick = -1; // Function to iterate at each vertex // to know at what point vertex enters // and get out static void Dfs(List< int >[] adj, int u, int p, int [] depth, int [] tour, int [] inTime, int [] outTime) { // When the vertex enters tour[++tick] = depth[u]; inTime[u] = tick; // Iterate for that particular vertex foreach ( int i in adj[u]) { // If it is not the parent if (i != p) { // Increment in depth i.e. distance depth[i] = depth[u] + 1; // Iterate for the child Dfs(adj, i, u, depth, tour, inTime, outTime); } } // When the vertex leaves tour[++tick] = depth[u]; outTime[u] = tick; } static List< int > Solve( int N, int Q, List< int []> Edge, List< int []> query) { // Initialize int N2 = 2 * N; List< int >[] adj = new List< int >[N]; for ( int i = 0; i < N; i++) { adj[i] = new List< int >(); } List< int > ans = new List< int >(); // To maintain distance for each vertex int [] depth = new int [N]; int [] euler = new int [N2]; // To maintain time of each vertex int [] inTime = new int [N]; int [] outTime = new int [N]; int [] pref = new int [N2]; int [] suff = new int [N2]; // To create an adjacency list for ( int i = 0; i < Edge.Count; i++) { adj[Edge[i][0]].Add(Edge[i][1]); adj[Edge[i][1]].Add(Edge[i][0]); } // Start iterating to maintain time Dfs(adj, 0, -1, depth, euler, inTime, outTime); pref[0] = euler[0]; suff[N2 - 1] = euler[N2 - 1]; // To add depth for each vertex to answer queries for ( int i = 1; i < N2; i++) { pref[i] = Math.Max(pref[i - 1], euler[i]); suff[N2 - i - 1] = Math.Max(suff[N2 - i], euler[N2 - i - 1]); } // Answering queries for ( int i = 0; i < query.Count; i++) { // To get parent and children if (depth[query[i][0]] < depth[query[i][1]]) { int temp = query[i][0]; query[i][0] = query[i][1]; query[i][1] = temp; } // Add the maximum depth ans.Add(Math.Max(pref[inTime[query[i][0]] - 1], suff[outTime[query[i][0]] + 1])); } return ans; } public static void Main( string [] args) { // Input int N = 3; int Q = 1; List< int []> Edge = new List< int []> { new int [] { 0, 1 }, new int [] { 0, 2 } }; List< int []> query = new List< int []> { new int [] { 0, 1 } }; // Function call List< int > ans = Solve(N, Q, Edge, query); int i = 0; while (i < ans.Count) { Console.Write(ans[i] + " " ); i++; } } } |
Javascript
function dfs(adj, u, p, depth, tour, in_time, out_time, tick) { // When vertex enters tick[0]++; tour[tick[0]] = depth[u]; in_time[u] = tick[0]; // Iterate for that particular vertex for (let i = 0; i < adj[u].length; i++) { // If it is not the parent if (adj[u][i] !== p) { // Increment in depth, i.e., distance depth[adj[u][i]] = depth[u] + 1; // Iterate for the child dfs(adj, adj[u][i], u, depth, tour, in_time, out_time, tick); } } // When vertex leaves tick[0]++; tour[tick[0]] = depth[u]; out_time[u] = tick[0]; } function solve(N, Q, Edge, query) { // Initialize const N2 = 2 * N; const adj = new Array(N).fill().map(() => []); const ans = []; // To maintain distance for each vertex const depth = new Array(N).fill(0); const euler = new Array(N2).fill(0); // To maintain time of each vertex const in_time = new Array(N).fill(0); const out_time = new Array(N).fill(0); const tick = [-1]; const pref = new Array(N2).fill(0); const suff = new Array(N2).fill(0); // To create an adjacency list for (const it of Edge) { adj[it[0]].push(it[1]); adj[it[1]].push(it[0]); } // Start iterating to maintain time dfs(adj, 0, -1, depth, euler, in_time, out_time, tick); pref[0] = euler[0]; suff[N2 - 1] = euler[N2 - 1]; // To add depth for each vertex to answer queries for (let i = 1; i < N2; i++) { pref[i] = Math.max(pref[i - 1], euler[i]); suff[N2 - i - 1] = Math.max(suff[N2 - i], euler[N2 - i - 1]); } // Answering queries for (const it of query) { // To get parent and children if (depth[it[0]] < depth[it[1]]) { [it[0], it[1]] = [it[1], it[0]]; } // Add the maximum depth ans.push(Math.max(pref[in_time[it[0]] - 1], suff[out_time[it[0]] + 1])); } return ans; } // Driver code const N = 3; const Q = 1; const Edge = [ [0, 1], [0, 2] ]; const query = [ [0, 1] ]; // Function call const ans = solve(N, Q, Edge, query); for (const a of ans) { process.stdout.write(a + " " ); } |
1
Time Complexity: O(N*log N)
Auxiliary Space: O(N)