[usth/MATH2.3] Mathemate Discretely

1 files changed, 55 insertions, 0 deletions

diff --git a/usth/MATH2.3/2/bipartite.cc b/usth/MATH2.3/2/bipartite.cc
new file mode 100644
index 0000000..49b8dfd
--- /dev/null
+++ b/usth/MATH2.3/2/bipartite.cc
@@ -0,0 +1,55 @@
+#include <iostream>
+#include <queue>
+#include <unordered_map>
+#include <set>
+
+using namespace std;
+
+int
+main ()
+{
+  unordered_map<size_t, unordered_map<size_t, size_t>> adj;
+  size_t n, u, v;
+  cin >> n;
+  while (n--)
+    {
+      cin >> u >> v;
+      adj[u][v]++;
+      adj[v][u]++;
+    }
+
+  queue<size_t> q;
+  set<size_t> one, another;
+  q.push (u);
+  one.insert (u);
+
+  while (!q.empty ())
+    {
+      u = q.front ();
+      q.pop ();
+      if (adj[u][u])
+        {
+          cout << "no" << endl;
+          return 0;
+        }
+      for (auto const& [v, b] : adj[u])
+        {
+          if (!b)
+            continue;
+          if (one.count (v) && one.count (u)
+              || another.count (v) && another.count (u))
+            {
+              cout << "no" << endl;
+              return 0;
+            }
+          if (one.count (v) || another.count (v))
+            continue;
+          q.push (v);
+          if (one.count (u))
+            another.insert (v);
+          else
+            one.insert (v);
+        }
+    }
+  cout << "yes" << endl;
+}