Problem of The Day: Reorder Routes to Make All Paths Lead to the City Zero

Problem Statement

leetcode problem link

My Solution [Accepted]

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = {i:[] for i in range(n)}
        direct_graph = {i:[] for i in range(n)}
        for src, des in connections:
            graph[src].append(des)
            graph[des].append(src)
            direct_graph[src].append(des)

        path_to_zero = 0
        stack = [0]
        visited = set()
        while stack:
            node = stack.pop()
            visited.add(node)
            for nei in graph[node]:
                if nei not in visited:
                    stack.append(nei)
                    if nei not in direct_graph[node]:
                        path_to_zero += 1

        return n - path_to_zero - 1

Editorial

Approach 1: Depth First Search

class Solution {
public:
    int count = 0;
    void dfs(int node, int parent, vector<vector<pair<int, int>>>& adj) {
        for (auto& [neighbor, sign] : adj[node]) {
            if (neighbor != parent) {
                count += sign;
                dfs(neighbor, node, adj);
            }
        }
    }

    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int, int>>> adj(n);
        for (auto& connection : connections) {
            adj[connection[0]].push_back({connection[1], 1});
            adj[connection[1]].push_back({connection[0], 0});
        }
        dfs(0, -1, adj);
        return count;
    }
};

Approach 2: Breadth First Search

class Solution {
public:
    int count = 0;
    void bfs(int node, int n, vector<vector<pair<int, int>>>& adj) {
        queue<int> q;
        vector<bool> visit(n);
        q.push(node);
        visit[node] = true;

        while (!q.empty()) {
            node = q.front();
            q.pop();
            for (auto& [neighbor, sign] : adj[node]) {
                if (!visit[neighbor]) {
                    count += sign;
                    visit[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
    }

    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int, int>>> adj(n);
        for (auto& connection : connections) {
            adj[connection[0]].push_back({connection[1], 1});
            adj[connection[1]].push_back({connection[0], 0});
        }
        bfs(0, n, adj);
        return count;
    }
};