aboutsummaryrefslogtreecommitdiff
path: root/other/reorder_route_city_zero.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/reorder_route_city_zero.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/reorder_route_city_zero.cpp')
-rw-r--r--other/reorder_route_city_zero.cpp48
1 files changed, 48 insertions, 0 deletions
diff --git a/other/reorder_route_city_zero.cpp b/other/reorder_route_city_zero.cpp
new file mode 100644
index 0000000..10ae61a
--- /dev/null
+++ b/other/reorder_route_city_zero.cpp
@@ -0,0 +1,48 @@
+// 1466. Reorder Routes to Make All Paths Lead to the City Zero
+#include "leetcode.h"
+
+/*
+ * there are 'n' cities numbered from 0 to 'n - 1' and 'n - 1'
+ * roads such that there is only one way to travel between two
+ * different cities (this network forms a tree). last year, the
+ * ministry of transport decided to orient the roads in one
+ * direction because they are too narrow.
+ * roads are represented by 'connections' where 'connections[i] = [ai, bi]'
+ * represents a road from city 'ai' to city 'bi'.
+ * this year, there will be a big event in the capital (city 0),
+ * and many people will want to travel to the city. task consists
+ * reorienting some roads such that each city can visit city 0.
+ * return minimum number of edges changed.
+ */
+
+class Solution {
+public:
+ int minReorder(int n, vvd & connections) {
+ vvd ans(n);
+ for (auto &c : connections) {
+ ans[c[0]].push_back(c[1]);
+ ans[c[1]].push_back(-c[0]);
+ }
+ return dfs(ans, vector<bool>(n) = {}, 0);
+ }
+
+private:
+ int dfs(vvd & res, vector<bool> visited, int from) {
+ auto change = 0;
+ visited[from] = true;
+ for (auto to : res[from])
+ if (!visited[abs(to)])
+ change += dfs(res, visited, abs(to)) + (to > 0);
+ return change;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd connections1 = {{0, 1}, {1, 3}, {2, 3}, {4, 0}, {4, 5}};
+ vvd connections2 = {{1, 0}, {1, 2}, {3, 2}, {3, 4}};
+ vvd connections3 = {{1, 0}, {2, 0}};
+ cout << obj.minReorder(6, connections1) << endl; // expect: 3
+ cout << obj.minReorder(5, connections2) << endl; // expect: 2
+ cout << obj.minReorder(3, connections3) << endl; // expect: 0
+}