Easy BFS Solution in JAVA in Depth
Key Idea\nSo the basic idea is to make the whole graph bidirectional , with an exception that the other edge will be a fake one (reverse of the edge given in co
**Key Idea**\nSo the basic idea is to make the whole graph bidirectional , with an exception that the other edge will be a fake one (*reverse of the edge given in connections list*) as shown below : \n\n\n\n![image](https://assets.leetcode.com/users/images/8c49d921-192f-4dd3-b990-9bd8dca03333_1599987352.8303022.png)\n\n\n\n\nAnd then perfom basic bfs operation on the graph with root as 0 and count the edge which is not Fake and going away from 0 **OR** going away from the nodes connected to 0 :\n\n\n![image](https://assets.leetcode.com/users/images/9647c95a-bb7f-431b-8b3a-2c6583e3a5a9_1599987973.8495517.png)\n\n\n\n**Algorithm**\n1. Make the whole graph bidirectional with fake edges.\n2. Start bfs with the root as 0.\n3. count the edge which is not fake and going away from 0 **OR** going away from  nodes connected to 0.\n4. return count\n\n\n\n\n**Implementation**\n\n\n```\nclass Solution {\n    public int minReorder(int n, int[][] connections) {\n        ArrayList<ArrayList<Pair>> adj = new ArrayList<>();\n        \n        for(int i = 0 ;i<n; i++){\n            adj.add(new ArrayList<Pair>());\n        }\n        \n        for(int ar[] : connections){\n            addEdge(adj, ar[0], ar[1]);\n        }\n        \n        return bfs(adj, n);\n    }\n    \n    \n    int bfs(ArrayList<ArrayList<Pair>> adj, int n){\n        boolean visited[] = new boolean[n];\n        \n        Queue<Integer> q = new LinkedList<>();\n        int count = 0;\n        q.add(0);\n        \n        while(!q.isEmpty()){\n            int temp = q.remove();\n            visited[temp] = true;\n            \n            for(Pair p : adj.get(temp)){\n                if(!visited[p.v]){\n                   // if the edge going away from zero/ nodes connected to 0 and is not fake then count ++\n                     if(p.isFake == false) count++; \n                    q.add(p.v);\n                }\n            }\n        }\n        \n        return count;\n    }\n    \n    \n    void addEdge(ArrayList<ArrayList<Pair>> adj, int u, int v){\n        adj.get(u).add(new Pair(v, false)); // this is the true edge \n\n        adj.get(v).add(new Pair(u, true)); // this is the fake edge\n    }\n}\n\n\nclass Pair{\n    int v; // the other node\n    boolean isFake = false; // is the edge fake or not\n    Pair(int v, boolean isFake){\n        this.v = v;\n        this.isFake = isFake;\n    }\n}\n```\n\n\n\n\n
['Breadth-First Search']