Unit 10 Session 2 Advanced (Click for link to problem statements)

• 💡 Difficulty: Medium
• ⏰ Time to complete: 30-40 mins
• 🛠️ Topics: Graph Traversal, DFS, Tree

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What does each connection in the connections array represent?
  • A: Each connection [airport_a, airport_b] represents a one-way flight from airport_a to airport_b.
• Q: What is the goal of the problem?
  • A: The goal is to reorient the minimum number of flights so that every airport can send a flight to airport 0.
• Q: How is the network of flights structured?
  • A: The network forms a tree, meaning there is exactly one path between any two airports.

HAPPY CASE Input: ```python n = 6 connections = [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]] ``` Output: ```markdown 3 Explanation: The initial flight routes are: 0 -> 1, 1 -> 3, 2 -> 3, 4 -> 0, 4 -> 5. To ensure every airport can send a flight to airport 0, we need to reorient the routes [1 -> 3], [2 -> 3], and [4 -> 5]. ``` EDGE CASE Input: ```python n = 2 connections = [[1, 0]] ``` Output: ```markdown 0 Explanation: The only flight already goes to airport 0, so no reorientation is needed. 

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Reorienting Directed Edges in a Tree, we want to consider the following approaches:

• Graph Traversal (DFS): We can traverse the graph and count how many directed edges need to be reversed so that every airport can reach airport 0.
• Tree Representation: Since the flight network forms a tree, we can use DFS to traverse the tree and determine which edges are incorrectly oriented.

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Convert the given one-way flight routes into an undirected graph representation. Then, use DFS to explore all airports, counting the number of edges that are directed away from airport 0 and need to be reversed. Every directed edge that goes away from 0 will require reorientation.

1) Build an adjacency list for the undirected graph from the `connections`. 2) Create a set `directed_edges` to store the original one-way flight routes. 3) Define a recursive DFS function: a) Traverse the graph, skipping the parent node to avoid revisiting. b) If an edge is directed away from airport `0`, increment the `reorient_count`. c) Recursively visit all connected airports. 4) Start DFS from airport `0` and count the number of reorientations. 5) Return the total `reorient_count`. 

⚠️ Common Mistakes

• Forgetting to track the direction of the original edges, which can lead to incorrect reorientation counting.
• Not handling the case where the tree is small (e.g., only one or two airports).

Implement the code to solve the algorithm.

def min_reorient_flight_routes(n, connections): # Create an adjacency list for the undirected graph graph = {i: [] for i in range(n)} directed_edges = set() # Store directed edges for a, b in connections: graph[a].append(b) graph[b].append(a) directed_edges.add((a, b)) # Mark the original direction # DFS to count the reorientations needed def dfs(airport, parent): nonlocal reorient_count # Explore all neighbors for neighbor in graph[airport]: if neighbor == parent: continue # Don't revisit the parent node # If the edge is directed away from 0 (wrong direction), increment the count if (airport, neighbor) in directed_edges: reorient_count += 1 # Recursively visit the neighbor dfs(neighbor, airport) reorient_count = 0 # Start DFS from airport 0 dfs(0, -1) return reorient_count

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input:

n = 6 connections = [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]] print(min_reorient_flight_routes(n, connections)) # Expected output: 3

• Output:

3

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

• Time Complexity: O(V + E), where V is the number of airports (vertices) and E is the number of flight routes (edges). Each airport and connection is visited once in the DFS traversal.
• Space Complexity: O(V + E) for storing the graph and directed edges.