
Description
The problem involves determining the minimum number of edges that need to be reversed in a directed graph so that every node is reachable from a starting node (node 0). The graph is represented by n
nodes and a list of connections
, where each connection is a directed edge between two nodes.
Intuition
The key insight is that if an edge is directed away from the starting node, it might need to be reversed to ensure that all nodes are reachable from node 0. By traversing the graph and counting such edges, we can determine the minimum number of reversals required.
Approach
- Graph Representation: First, we represent the graph using an adjacency list, where each node points to its connected nodes. We use a positive value for edges that are already correctly oriented and a negative value for edges that might need to be reversed.
- Depth-First Search (DFS): Starting from node 0, we traverse the graph using DFS. During the traversal, we keep track of visited nodes to avoid cycles and unnecessary computations.
- Edge Evaluation: For each edge, if the edge is negatively valued (indicating a possible reversal), we increment our reversal count. If the edge is positively valued, we continue the DFS traversal without incrementing the count.
- Return the Result: The final count after the DFS traversal will give us the minimum number of edges that need to be reversed.
Complexity
Time Complexity:
O(N + E), where N is the number of nodes and E is the number of edges. We traverse each node and edge once.
Space Complexity:
O(N + E), where N is for storing the visited nodes and E is for the adjacency list representing the graph.
Code
C++
class Solution {
public:
int minReorder(int n, vector>& connections) {
vector> grid(n);
vector vis(n, 0);
for (const auto& conn : connections) {
int src = conn[0];
int dest = conn[1];
grid[src].push_back(-1 * dest);
grid[dest].push_back(src);
}
return solve(grid, 0, vis);
}
private:
int solve(vector>& grid, int val, vector& vis) {
if (vis[val] == 1) {
return 0;
}
int ans = 0;
vis[val] = 1;
for (int ele : grid[val]) {
if (vis[abs(ele)] == 1) {
continue;
}
if (ele < 0) {
ans += 1;
}
ans += solve(grid, abs(ele), vis);
}
return ans;
}
};
Python
class Solution:
def minReorder(self, n, connections):
grid = [[] for _ in range(n)]
vis = [False] * n
for src, dest in connections:
grid[src].append(-dest)
grid[dest].append(src)
return self.solve(grid, 0, vis)
def solve(self, grid, val, vis):
if vis[val]:
return 0
ans = 0
vis[val] = True
for ele in grid[val]:
if vis[abs(ele)]:
continue
if ele < 0:
ans += 1
ans += self.solve(grid, abs(ele), vis)
return ans
# Example usage:
sol = Solution()
n = 6
connections = [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]]
print(sol.minReorder(n, connections))
Java
public class Solution {
private int solve(List> grid, int val, boolean[] vis) {
if (vis[val]) {
return 0;
}
int ans = 0;
vis[val] = true;
for (int ele : grid.get(val)) {
if (vis[Math.abs(ele)]) {
continue;
}
if (ele < 0) {
ans += 1;
}
ans += solve(grid, Math.abs(ele), vis);
}
return ans;
}
public int minReorder(int n, int[][] connections) {
List> grid = new ArrayList<>();
boolean[] vis = new boolean[n];
for (int i = 0; i < n; i++) {
grid.add(new ArrayList<>());
}
for (int[] conn : connections) {
int src = conn[0];
int dest = conn[1];
grid.get(src).add(-1 * dest);
grid.get(dest).add(src);
}
return solve(grid, 0, vis);
}
public static void main(String[] args) {
Solution solution = new Solution();
int n = 6;
int[][] connections = {{0, 1}, {1, 3}, {2, 3}, {4, 0}, {4, 5}};
System.out.println(solution.minReorder(n, connections));
}
}
JavaScript
var minReorder = function (n, connections) {
let adj = [], grid = [], vis = [], len = connections.length;
for (let i = 0; i < n; i++) {
grid.push([]);
vis[i] = 0;
}
for (let i = 0; i < len; i++) {
let src = connections[i][0];
let dest = connections[i][1];
grid[src].push(-1 * dest);
grid[dest].push(src);
}
console.log(grid);
return solve(grid, 0, vis);
};
function solve(grid, val, vis) {
if (vis[val] === 1) {
return 0;
}
let ans = 0;
vis[val] = 1;
for (let i = 0; i < grid[val].length; i++) {
let ele = grid[val][i];
if (vis[Math.abs(ele)] == 1) {
continue;
}
if (ele < 0) {
ans += 1;
}
ans += solve(grid, Math.abs(ele), vis);
}
return ans;
}