Java | DFS | BSF | Beats 92%
Approach\n- minus(-) represents opposite direction. \n\n# Time Complexity\n \nO(n)\n\n\n\n# 1.DFS\njava\nclass Solution {\n    int count =0;\n\n    public int m
# Approach\n- minus(-) represents opposite direction. \n\n# Time Complexity\n \n$$O(n)$$\n\n\n\n# 1.DFS\n```java\nclass Solution {\n    int count =0;\n\n    public int minReorder(int n, int[][] connections) {\n        boolean visit[] = new boolean[n];\n        List<List<Integer>> graph = new ArrayList<>();\n\n        for (int i = 0; i < n; i++) \n            graph.add(i, new ArrayList<>());\n        \n        for (int[] nums : connections) {\n            graph.get(nums[0]).add(nums[1]);\n            graph.get(nums[1]).add(-nums[0]);\n        }\n        dfs(graph, visit, 0);\n        return count;\n    }\n\n    private void dfs(List<List<Integer>> graph, boolean[] visit, int i) {\n        if (!visit[i]) {\n            visit[i] = true;\n            for (int num : graph.get(i)) {\n                int absNum = Math.abs(num);\n                if (!visit[absNum]) {\n                    if (num > 0) \n                        count++;                    \n                    dfs(graph, visit, absNum);\n                }\n            }\n        }\n    }\n\n}\n```\n\n# 2. BFS\n\n```java\nclass Solution {    \n    public int minReorder(int n, int[][] connections) {\n        boolean[] visit = new boolean[n];\n        List<List<Integer>> graph = new ArrayList<>();\n\n        for (int i = 0; i < n; i++) {\n            graph.add(i, new ArrayList<>());\n        }\n\n        for (int[] nums : connections) {\n            graph.get(nums[0]).add(nums[1]);\n            graph.get(nums[1]).add(-nums[0]);\n        }\n\n        int count = 0;\n\n        visit[0] = true;\n        Deque<Integer> queue = new LinkedList<>();\n        queue.offer(0);\n\n        while (!queue.isEmpty()) {\n            int pop = Math.abs(queue.pop());\n            for (Integer num : graph.get(pop)) {\n                if (!visit[Math.abs(num)]) {\n                    if (num > 0) {\n                        count++;\n                    }\n                    visit[Math.abs(num)] = true;\n                    queue.offer(num);\n                }\n            }\n        }\n\n        return count;\n    }\n}\n```\n\n\n<br/>\n\n<img src="https://assets.leetcode.com/users/images/085853ae-9586-479f-acf2-ec3ce30fd0e7_1703932262.0024223.png" style="width:400px;height:auto;">\n\n<br/>
['Java']