From a3dd2581ed4847670f81157091016c14ca18803d Mon Sep 17 00:00:00 2001
From: Nguyễn Gia Phong <vn.mcsinyx@gmail.com>
Date: Tue, 14 Jan 2020 18:29:11 +0700
Subject: [usth/MATH2.3] Mathemate Discretely

---
 usth/MATH2.3/3/st-dfs.cc | 44 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)
 create mode 100644 usth/MATH2.3/3/st-dfs.cc

(limited to 'usth/MATH2.3/3/st-dfs.cc')

diff --git a/usth/MATH2.3/3/st-dfs.cc b/usth/MATH2.3/3/st-dfs.cc
new file mode 100644
index 0000000..89814dd
--- /dev/null
+++ b/usth/MATH2.3/3/st-dfs.cc
@@ -0,0 +1,44 @@
+#include <iostream>
+#include <unordered_map>
+
+using namespace std;
+
+void
+dfs (unordered_map<size_t, unordered_map<size_t, int>>& graph, 
+     unordered_map<size_t, int>& been, size_t current)
+{
+  been[current] = 1;
+  for (auto const& [i, b] : graph[current])
+    if (b > 0)
+      if (been[i])
+        graph[current][i] = graph[i][current] = 0;
+      else
+        {
+          graph[current][i] = graph[i][current] = -1;
+          dfs (graph, been, i);
+        }
+}
+
+int
+main ()
+{
+  size_t n;
+  unordered_map<size_t, unordered_map<size_t, int>> edges;
+
+  cin >> n;
+  for (size_t i = 0; i < n; ++i)
+    for (size_t j = 0; j < n; ++j)
+      {
+        cin >> edges[i][j];
+        edges[j][i] = edges[i][j];
+      }
+
+  unordered_map<size_t, unordered_map<size_t, int>> st;
+  unordered_map<size_t, int> been;
+  dfs (edges, been, 0);
+
+  for (auto const& [i, m] : edges)
+    for (auto const& [j, b] : m)
+      if (b && i <= j)
+        cout << i << " " << j << endl;
+}
-- 
cgit 1.4.1