[usth/MATH2.3] Mathemate Discretely

1 files changed, 44 insertions, 0 deletions

diff --git a/usth/MATH2.3/2/connected.cc b/usth/MATH2.3/2/connected.cc
new file mode 100644
index 0000000..0659094
--- /dev/null
+++ b/usth/MATH2.3/2/connected.cc
@@ -0,0 +1,44 @@
+#include <iostream>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+using namespace std;
+
+int
+main ()
+{
+  size_t n, a, b;
+  unordered_map<size_t, unordered_set<size_t>> edges;
+
+  cin >> n;
+  for (size_t i = 0; i < n; ++i)
+    {
+      cin >> a >> b;
+      edges[a].insert (b);
+      edges[b].insert (a);
+    }
+
+  unordered_set<size_t> s;
+  size_t count = 0;
+  for (auto const& [v, p] : edges)
+    {
+      if (s.count (v))
+        continue;
+      count++;
+      vector<size_t> fifo {v};
+      while (!fifo.empty ())
+        {
+          size_t u = fifo.back ();
+          fifo.pop_back ();
+          if (s.count (u))
+            continue;
+          s.insert (u);
+          for (auto const& w : edges[u])
+            if (!s.count (w))
+              fifo.push_back (w);
+        }
+    }
+
+  cout << count << endl;
+}