aboutsummaryrefslogtreecommitdiff
path: root/other/valid_arrangement_pairs.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/valid_arrangement_pairs.cpp')
-rw-r--r--other/valid_arrangement_pairs.cpp73
1 files changed, 0 insertions, 73 deletions
diff --git a/other/valid_arrangement_pairs.cpp b/other/valid_arrangement_pairs.cpp
deleted file mode 100644
index 0493141..0000000
--- a/other/valid_arrangement_pairs.cpp
+++ /dev/null
@@ -1,73 +0,0 @@
-// 2097. Valid Arrangement of Pairs
-#include "leetcode.h"
-
-/*
- * you are given a 0-indexed 2d integer array 'pairs' where 'pairs[i] =
- * [start_i, end_i]'. an arrangement of 'pairs' is valid for every index 'i'
- * where '1 <= i < pairs.length', we have 'end_i-1 == start_i'. return any valid
- * arrangement of 'pairs'. note, the inputs will be generated such that there
- * exists a valid arrangement of 'pairs'.
- */
-
-class Solution {
-private:
- void euler(unordered_map<int, stack<int>> &adj, vector<vector<int>> &res,
- int curr) {
- auto &st = adj[curr];
- while (!st.empty()) {
- int n = st.top();
- st.pop();
- euler(adj, res, n);
- res.push_back({curr, n});
- }
- }
-
-public:
- vector<vector<int>> validArrangement(vector<vector<int>> &pairs) {
- int m = pairs.size();
- unordered_map<int, stack<int>> adj;
- unordered_map<int, int> in, out;
- adj.reserve(m);
- in.reserve(m);
- out.reserve(m);
- for (int i = 0; i < m; i++) {
- int u = pairs[i][0], v = pairs[i][1];
- in[v]++;
- out[u]++;
- adj[u].push(v);
- }
- int start = -1;
- for (auto &p : adj) {
- int i = p.first;
- if (out[i] - in[i] == 1)
- start = i;
- }
- if (start == -1)
- start = adj.begin()->first;
- vector<vector<int>> ans;
- euler(adj, ans, start);
- reverse(ans.begin(), ans.end());
- return ans;
- }
-};
-
-int main() {
- Solution obj;
- vvd p1 = {{5, 1}, {4, 5}, {11, 9}, {9, 4}},
- p2 = {{1, 3}, {3, 2}, {2, 1}}, p3 = {{1, 2}, {1, 3}, {2, 1}};
- vvd va1 = obj.validArrangement(p1);
- vvd va2 = obj.validArrangement(p2);
- vvd va3 = obj.validArrangement(p3);
- for (int i = 0; i < va1.size(); i++)
- for (int j = 0; j < va1[0].size(); j++)
- printf("%d ", va1[i][j]); // expect: [[11,9],[9,4],[4,5],[5,1]]
- printf("\n");
- for (int i = 0; i < va2.size(); i++)
- for (int j = 0; j < va2[0].size(); j++)
- printf("%d ", va2[i][j]); // expect: [[1,3],[3,2],[2,1]]
- printf("\n");
- for (int i = 0; i < va3.size(); i++)
- for (int j = 0; j < va3[0].size(); j++)
- printf("%d ", va1[i][j]); // expect: [[1,2],[2,1],[1,3]]
- printf("\n");
-}