Clean DFS + BFS Solution With Explanation (O(n^2) || O(n) time)
Idea\n- The main idea of both solutions is that we will necessarily traverse from zero, visiting the node closest to it (even if we cannot reach it from zero) a
# Idea\n- The main idea of both solutions is that we will necessarily traverse from zero, visiting the node closest to it (even if we cannot reach it from zero) and so on. If a node is directed to zero, ans is not incremented, otherwise ans++.\n- First we convert the given array into an adjacent list with a specific feature. It is important for us to store for each node not only where we can go from it, but also how we can visit it. But how do we figure out which node we can come to from a given node, and which leads to this node? We will add those nodes that we can visit with +, others with -\n\n```\ngraph := make([][]int, n)\n    for _, val := range connection{\n        graph[val[0]] = append(graph[val[0]], val[1]) // where we can go\n        graph[val[1]] = append(graph[val[1]], -val[0]) //where we can come from\n    }\n```\n- Then create a **visited-array**, in which we will store those nodes that we have already visited. The answer will be stored in the **ans** variable\n ```\nvisited := make([]bool, n)\nans := 0\n```\n\n# First Approach (DFS)\n- Let\'s create a classic DFS for graph traversal with a slight modification. We pass the current Node to the function, immediately write its values to visited[node] = true. \n- Next, we traverse all nodes that are related to the data in one way or another. \n- If it hasn\'t been visited yet, we run recursively dfs from its value. If the value was negative, then ans unchanged, otherwise ans++ (Node direction). \n```\nvar dfs func(number int)\n    dfs = func(number int){\n        visited[number] = true \n        for i:=0; i<len(graph[number]); i++{\n            if !visited[abs(graph[number][i])]{\n                dfs(abs(graph[number][i]))\n                if graph[number][i] >0{ // check node direction\n                    ans++\n                }\n            }\n        }\n    }\n```\n- Then iteratively go through all nodes in the graph. If it has not been visited yet, run dfs from it\n\n\n#### Full Code (DFS)\n```\nfunc minReorder(n int, con [][]int) int {\n    visited := make([]bool, n)\n    graph := make([][]int, n)\n    for _, val := range con{\n        graph[val[0]] = append(graph[val[0]], val[1])\n        graph[val[1]] = append(graph[val[1]], -val[0])\n    }\n    ans:=0\n    var dfs func(number int)\n    dfs = func(number int){\n        visited[number] = true\n        for i:=0; i<len(graph[number]); i++{\n            if !visited[abs(graph[number][i])]{\n                dfs(abs(graph[number][i]))\n                if graph[number][i] >0{\n                    ans++\n                }\n            }\n        }\n    }\n    for i:=0; i<len(graph); i++{\n        if !visited[i]{\n            dfs(i)\n        }\n    }\n    return ans\n}\n\nfunc abs(a int) int{\n    if a>=0{\n        return a\n    }\n    return -a\n}\n```\n# Second solution (BFS)\n- The idea of the solution is the same as in the first one (looking at the node direction). We create a queue to which we sequentially add all nodes that are somehow related to the given node. Depending on the value of the node (positive or negative) we increase ans or leave it as it is. Mark this Node as visited. \n## Full code (BFS)\n```\nfunc minReorder(n int, con [][]int) int {\n    visited := make([]bool, n)\n    graph := make([][]int, n)\n    for _, val := range con{\n        graph[val[0]] = append(graph[val[0]], val[1])\n        graph[val[1]] = append(graph[val[1]], -val[0])\n    }\n    queue := []int{}\n    for _, val := range graph[0]{\n        queue = append(queue, val)\n    }\n\n    ans:=0\n    for len(queue) > 0{\n        size := len(queue)\n        for i:=0; i<size; i++{\n            cur := queue[0]\n            queue = queue[1:]\n            if cur > 0 && !visited[abs(cur)]{\n                ans++\n            }\n            if len(graph[abs(cur)]) > 0 && !visited[abs(cur)]{\n                for _, val := range graph[abs(cur)]{\n                    queue = append(queue, val)\n                }\n            }\n            visited[abs(cur)] = true\n        }\n\n    }\n    return ans\n\n}\nfunc abs(a int) int{\n    if a>=0{\n        return a\n    }\n    return -a\n}\n```\n## If you hava any question, feel free to ask. If you like the solution or the explaination, Please UPVOTE!
['Depth-First Search', 'Breadth-First Search', 'Graph', 'Go']