BEATS 99% in time and 78% in space C# solution. DFS and BFS solution. Well commented.
General intuition\nThe logic is the same as that from the editorial solution. I just thought I\'d made this C# code much more readable and easy to understand. \
# General intuition\nThe logic is the same as that from the editorial solution. I just thought I\'d made this C# code much more readable and easy to understand. \n\nWe\'re basically doing a traversal. Since **all roads** need to **lead from other cities to 0**, if we traverse using an original edge away from zero, that edge should be removed => all original edges should have a weight of 1 and fake edges (edges in reverse that we add for the express purpose of traversing the tree) should have a weight of 0.\n\n# Approach 1: DFS\nNothing fancy, just regular DFS. No need for any seen data stracture since it\'s a tree anyway.\n\n# Algorithm\n- Use an adjList to store the graph. Put `ai -> bi` as the original road and give it a weight of 1. \n- Put `bi -> ai` also in the list with a weight of 0.\n- DFS from 0 and at every step keep incrementing count using sign.\n- No need for any seen/cache data structure to prevent looping. Since it\'s given that the input is a tree like structure, only need to make sure we don\'t loop between parent and child => just skip over DFS when we encounter parent in the connection list of child.\n\n# Complexity\n- Time complexity: `O(n)` since we visit each node once to explore it\n\n- Space complexity: `O(h)` at max height of the tree will be in the stack at any one time.\n\n# Code\n```\npublic class Solution {\n    public int MinReorder(int n, int[][] roads) {\n        //graph is defined as an adjList with sign to denote if original (1) or fake (0) road\n        // and connection to denote which city that road leads to\n        List<List<(int sign, int conn)>> adj = new(); int count = 0;\n\n        //Initialization\n        for(int i = 0; i < n; i++){ adj.Add(new List<(int sign, int conn)>()); }\n\n        //Populating\n        foreach(int[] road in roads){\n            adj[road[0]].Add((1, road[1])); //Adding original road\n            adj[road[1]].Add((0, road[0])); //Adding fake road\n        }\n\n        DFS(0, -1); //DFS from 0. \n\n        return count;\n\n        void DFS(int curr, int par){            \n            foreach((int sign, int conn) nei in adj[curr]){\n                if(nei.conn == par) continue; //Don\'t want to go in a loop => skip parent in child\n\n                count += nei.sign; //Keep adding sign\n                DFS(nei.conn, curr); //Do DFS on child using curr as parent\n            }\n        }\n    }\n}\n```\n\n# Approach 2: BFS\nSimple, bare-bones BFS traversal. Simply count the number of nodes going away from the 0 (original nodes) each time we explore. That\'s it.\n\n# Algorithm\n- Use an adjList to store the graph. Put `ai -> bi` as the original road and give it a weight of 1. \n- Put `bi -> ai` also in the list with a weight of 0.\n- The queue in the BFS traversal should have the current and the parent node so that we can know what the parent is of the current node to prevent looping.\n\n# Complexity\n- Time complexity: `O(n)` since we visit each node once to explore it\n\n- Space complexity: `O(w)` at max width of the tree will be in the queue at any one time.\n\n# Code\n```\npublic class Solution {\n    public int MinReorder(int n, int[][] roads) {\n        List<List<(int sign, int conn)>> adj = new(); int count = 0;\n\n        for(int i = 0; i < n; i++){ adj.Add(new List<(int sign, int conn)>()); }\n        foreach(int[] pair in roads){\n            adj[pair[0]].Add((1, pair[1])); //Original road is given a weight of 1\n            adj[pair[1]].Add((0, pair[0])); //Fake/Aritifical road is given a weight of 0\n        }\n\n        //Doing BFS\n        //Need to keep track of parent to prevent infinite loop\n        Queue<(int node, int par)> queue = new(); queue.Enqueue((0, -1));\n        while(queue.Count > 0){\n            int size = queue.Count;\n            for(int i = 0; i < size; i++){\n                (int curr, int par) = queue.Dequeue();\n                foreach(var entry in adj[curr]){\n                    if(entry.conn == par) continue; //Skipping parent\n                    \n                    count += entry.sign; //Keeping count of all roads leading away from 0\n                    queue.Enqueue((entry.conn, curr)); //Adding in queue for further processing\n                }\n            }\n        }\n\n        return count;\n    }\n}\n```\n# Approach 3: DFS and BFS variation\nThis is a variation that BingChat gave me to this question. It involves setting the value of the real edge as +ve and the fake edge as -ve rather than attach another flag to it. Pretty compact. Same complexities. \n\n```\npublic class Solution {\n    public int MinReorder(int n, int[][] roads) {\n        //Adjacency List declaration\n        List<int>[] adj = new List<int>[n];\n        for(int i = 0 ; i < n; i++){ adj[i] = new List<int>(); }\n\n        //Original and fake roads should be differentiated.\n        // Put +ve for original road and -ve for fake road\n        foreach(int[] road in roads){ \n            adj[road[0]].Add(road[1]); adj[road[1]].Add(-road[0]); \n        }\n\n        //Perform BFS\n        Queue<(int curr, int par)> queue = new(); queue.Enqueue((0, -1));\n        int count = 0;\n        while(queue.Count > 0){\n            int size = queue.Count;\n            for(int i = 0; i < size; i++){\n                (int curr, int par) = queue.Dequeue();\n\n                foreach(int entry in adj[curr]){\n                    if(Math.Abs(entry) == par) continue;\n\n                    if(entry > 0) { count++; }\n                    queue.Enqueue((Math.Abs(entry), curr));\n                }\n            }\n        }\n\n        return count; //Comment from line 13-30 and you can get the DFS approach\n\n        return DFS(0, -1); //Start DFS from 0 to count roads leading away from zero\n\n        int DFS(int curr, int par){\n            int count  = 0; //Keep count of how many nodes from this node need to be changed\n            foreach(int nei in adj[curr]){\n                if(Math.Abs(nei) == par) continue; //Skip over parent to prevent self loop\n\n                if(nei > 0){ count++; } //If edge is original => add count\n                count += DFS(Math.Abs(nei), curr); //Incrementing node count\n            }\n            return count;\n        }\n    }\n}\n```
['Depth-First Search', 'Breadth-First Search', 'Graph', 'C#']