Simple Explanation | DFS with edge deletion | Idea | Code | Comments | Q & A
Key Idea\nThe base case that we know is - All outgoing edges from 0 must be reversed. So add the count into our final result. \nAt this stage, we can say all ed
**Key Idea**\nThe base case that we know is - All outgoing edges from 0 must be reversed. So add the count into our final result. \nAt this stage, we can say all edges are coming into node 0. What is the next thing we need to do?\nMake sure that all nodes that are connected to 0 have all edges coming into them.\nE.g. if nodes x and y are connected to 0. After first step, there will be edges from x to 0 and y to 0. Now we want to make sure that all nodes that are directly connected to x, must have an edge coming into x. Similarly for y. If we keep on doing this recursively, we will get the answer at the end. Along the way, we will keep counting the edges that we reversed.\n\n**Implementation**\nFor the ease of implementation, I have created two separate graph, one for outgoing edges and another for incoming. Everytime an edge is traversed, I erase the opposite edge so that I don\u2019t hit the same node twice.\n\n**Time Complexity** \nO(n) where n is number of nodes in the tree.\n\n**Thanks**\nIs there anything that is still unclear? Let me know and I can elaborate. \nPlease upvote if you find this helpful, it will be encouraging.\n\n**Q&A**\n```\nQ1. \n\n// Why we need to traverse both incoming as well as outgoing edges?\n// Ans. \n// We want all edges to come towards 0. Reversing outgoing edges\n// from 0 is necessary - you can understand this easily.\n// Then you need to recursively orient all outgoing edges from \n// those connected nodes too.\n// But why do we need to recursively call dfs() even for incoming\n// edges? \n// The answer is, we don\'t know the orientation of edges that are \n// connected to that neighbor node.\n// For example - say 0 has an incoming edge from 1 and 1 has one other\n// outgoing edge to 2. i.e. graph is like 0 <-- 1 --> 2.\n// Although, you don\'t need to reverse 0 <-- 1 edge, you still have to \n// make sure that all other edges are coming towards 1. When you call\n// dfs with node 1, you will then recognize the incorrect orientation\n// of 1 --> 2 edge. This is why traversing incoming edges is important.\n```\n```\nQ2.\n\n// Why do we need to erase edges?\n// Ans.\n// To avoid double counting. \n// We increment the count everytime we see an outgoing edge. We don\'t \n// increment for incoming. However, an incoming edge for one node is \n// the outgoing edge for the other.\n// In the previous example, 0 <-- 1 --> 2.\n// For node 0, we won\'t increment the count because there are no outgoing\n// edges. But when we are at 1, there are two outgoing edges. But 1 --> 0 \n// is already oriented towards 0 and we don\'t want to reverse that. How \n// will we distiguish between correctly oriented edges vs incorrectly \n// oriented ones in general? Easier approach is to remove those correctly \n// oriented edges immediately when we know their orientation is correct.\n```\n\n\n\n**Code**\nC++\n```\nclass Solution {\npublic:\n    unordered_map<int, unordered_set<int>> out, in;\n    int ans = 0;\n    \n    void dfs(int node) {\n        \n        // Why we need to traverse both incoming as well as outgoing edges?\n        // Ans. \n        // We want all edges to come towards 0. Reversing outgoing edges\n        // from 0 is necessary - you can understand this easily.\n        // Then you need to recursively orient all outgoing edges from \n        // those connected nodes too.\n        // But why do we need to recursively call dfs() even for incoming\n        // edges? \n        // The answer is, we don\'t know the orientation of edges that are \n        // connected to that neighbor node.\n        // For example - say 0 has an incoming edge from 1 and 1 has one other\n        // outgoing edge to 2. i.e. graph is like 0 <-- 1 --> 2.\n        // Although, you don\'t need to reverse 0 <-- 1 edge, you still have to \n        // make sure that all other edges are coming towards 1. When you call\n        // dfs with node 1, you will then recognize the incorrect orientation\n        // of 1 --> 2 edge. This is why traversing incoming edges is important.\n        \n        // Why do we need to erase edges?\n        // Ans.\n        // To avoid double counting. \n        // We increment the count everytime we see an outgoing edge. We don\'t \n        // increment for incoming. However, an incoming edge for one node is \n        // the outgoing edge for the other.\n        // In the previous example, 0 <-- 1 --> 2.\n        // For node 0, we won\'t increment the count because there are no outgoing\n        // edges. But when we are at 1, there are two outgoing edges. But 1 --> 0 \n        // is already oriented towards 0 and we don\'t want to reverse that. How \n        // will we distiguish between correctly oriented edges vs incorrectly \n        // oriented ones in general? Easier approach is to remove those correctly \n        // oriented edges immediately when we know their orientation is correct.\n        \n        for (int x: out[node]) {\n            // There is an edge (node->x). We must reverse it.\n            ans++; \n\t\t\t// delete, edge (x <- node)\n            in[x].erase(node);\n\t\t\t// recurse.\n            dfs(x);\n        }\n        for (int x:in[node]) {\n\t\t    // The edge is (x <- node). So delete (node -> x).\n\t\t\tout[x].erase(node);\n\t\t\t// recurse.\n            dfs(x);\n        }\n    }\n    \n    int minReorder(int n, vector<vector<int>>& connections) {\n        ans = 0;\n\t\t// make graph.\n        for (auto x: connections) {\n            out[x[0]].insert(x[1]);\n            in[x[1]].insert(x[0]);\n        }\n\t\t// start with node 0.\n        dfs(0);\n        return ans;\n    }\n};\n```\n\n**Did you check the visuals of the other problem in the contest?**\nhttps://leetcode.com/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/discuss/661995/\n
['Depth-First Search']