FPEvalDataset/LeetCodeProblem
0304
1{2 "id": 3105,3 "name": "minimum_edge_reversals_so_every_node_is_reachable",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/minimum-edge-reversals-so-every-node-is-reachable/",6 "date": "2023-09-02 00:00:00",7 "task_description": "There is a **simple directed graph** with `n` nodes labeled from `0` to `n - 1`. The graph would form a **tree** if its edges were bi-directional. You are given an integer `n` and a **2D** integer array `edges`, where `edges[i] = [ui, vi]` represents a **directed edge** going from node `ui` to node `vi`. An **edge reversal** changes the direction of an edge, i.e., a directed edge going from node `ui` to node `vi` becomes a directed edge going from node `vi` to node `ui`. For every node `i` in the range `[0, n - 1]`, your task is to **independently** calculate the **minimum** number of **edge reversals** required so it is possible to reach any other node starting from node `i` through a **sequence** of **directed edges**. Return _an integer array _`answer`_, where _`answer[i]`_ is the__ _ _**minimum** number of **edge reversals** required so it is possible to reach any other node starting from node _`i`_ through a **sequence** of **directed edges**._ **Example 1:** ``` **Input:** n = 4, edges = [[2,0],[2,1],[1,3]] **Output:** [1,1,0,2] **Explanation:** The image above shows the graph formed by the edges. For node 0: after reversing the edge [2,0], it is possible to reach any other node starting from node 0. So, answer[0] = 1. For node 1: after reversing the edge [2,1], it is possible to reach any other node starting from node 1. So, answer[1] = 1. For node 2: it is already possible to reach any other node starting from node 2. So, answer[2] = 0. For node 3: after reversing the edges [1,3] and [2,1], it is possible to reach any other node starting from node 3. So, answer[3] = 2. ``` **Example 2:** ``` **Input:** n = 3, edges = [[1,2],[2,0]] **Output:** [2,0,1] **Explanation:** The image above shows the graph formed by the edges. For node 0: after reversing the edges [2,0] and [1,2], it is possible to reach any other node starting from node 0. So, answer[0] = 2. For node 1: it is already possible to reach any other node starting from node 1. So, answer[1] = 0. For node 2: after reversing the edge [1, 2], it is possible to reach any other node starting from node 2. So, answer[2] = 1. ``` **Constraints:** `2 <= n <= 105` `edges.length == n - 1` `edges[i].length == 2` `0 <= ui == edges[i][0] < n` `0 <= vi == edges[i][1] < n` `ui != vi` The input is generated such that if the edges were bi-directional, the graph would be a tree.",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "n = 4, edges = [[2,0],[2,1],[1,3]]",12 "output": "[1,1,0,2] "13 },14 {15 "label": "Example 2",16 "input": "n = 3, edges = [[1,2],[2,0]]",17 "output": "[2,0,1] "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 10,24 [25 [26 0,27 128 ],29 [30 0,31 232 ],33 [34 1,35 336 ],37 [38 3,39 440 ],41 [42 3,43 544 ],45 [46 2,47 648 ],49 [50 2,51 752 ],53 [54 0,55 856 ],57 [58 0,59 960 ]61 ]62 ],63 "output": [64 0,65 1,66 1,67 2,68 3,69 3,70 2,71 2,72 1,73 174 ]75 },76 {77 "input": [78 9,79 [80 [81 0,82 183 ],84 [85 0,86 287 ],88 [89 0,90 391 ],92 [93 0,94 495 ],96 [97 3,98 599 ],100 [101 2,102 6103 ],104 [105 2,106 7107 ],108 [109 5,110 8111 ]112 ]113 ],114 "output": [115 0,116 1,117 1,118 1,119 1,120 2,121 2,122 2,123 3124 ]125 },126 {127 "input": [128 5,129 [130 [131 0,132 1133 ],134 [135 0,136 2137 ],138 [139 2,140 3141 ],142 [143 3,144 4145 ]146 ]147 ],148 "output": [149 0,150 1,151 1,152 2,153 3154 ]155 },156 {157 "input": [158 9,159 [160 [161 0,162 1163 ],164 [165 0,166 2167 ],168 [169 0,170 3171 ],172 [173 0,174 4175 ],176 [177 3,178 5179 ],180 [181 5,182 6183 ],184 [185 3,186 7187 ],188 [189 7,190 8191 ]192 ]193 ],194 "output": [195 0,196 1,197 1,198 1,199 1,200 2,201 3,202 2,203 3204 ]205 },206 {207 "input": [208 9,209 [210 [211 0,212 1213 ],214 [215 1,216 2217 ],218 [219 1,220 3221 ],222 [223 0,224 4225 ],226 [227 3,228 5229 ],230 [231 2,232 6233 ],234 [235 0,236 7237 ],238 [239 2,240 8241 ]242 ]243 ],244 "output": [245 0,246 1,247 2,248 2,249 1,250 3,251 3,252 1,253 3254 ]255 }256 ],257 "haskell_template": "minEdgeReversals :: Int -> [[Int]] -> [Int]\nminEdgeReversals n edges ",258 "ocaml_template": "let minEdgeReversals (n: int) (edges: int list list) : int list = ",259 "scala_template": "def minEdgeReversals(n: Int,edges: List[List[Int]]): List[Int] = { \n \n}",260 "java_template": "class Solution {\n public int[] minEdgeReversals(int n, int[][] edges) {\n \n }\n}",261 "python_template": "class Solution(object):\n def minEdgeReversals(self, n, edges):\n \"\"\"\n :type n: int\n :type edges: List[List[int]]\n :rtype: List[int]\n \"\"\"\n "262}