7 files changed, 264 insertions, 0 deletions
diff --git a/usth/MATH2.3/2/README.md b/usth/MATH2.3/2/README.md
new file mode 100644
index 0000000..df599a5
--- /dev/null
+++ b/usth/MATH2.3/2/README.md
@@ -0,0 +1,59 @@
+# Graphs
+## Problem 1
+`bipartite.cc` (C++17) takes an natural number `n` of edges and `n` lines
+of pairs of connected vertices from stdin and print either `yes` or `no` to
+stdout if the given graph is or is not bipartite respectively.
+
+## Problem 2
+`adjmat2edges.cc` takes an natural number `n` and a `n`-by-`n` adjacent matrix
+of natural numbers from stdin and print triplets (`u`, `v`, `m`) separated by
+spaces to stdout, where `u`, `v` are vertices and `m > 0` is the number of edges
+connecting these two.
+
+## Problem 3
+`incidentmat2edges.cc` take 2 natural numbers `v`, `e` and a `v`-by-`e`
+incidental matrix from stdin and print each edge along with number of its
+appearance to stdout, e.g.
+
+### Input
+    2 2
+    1 1
+    1 1
+
+### Output
+    0 1 2
+
+## Problem 4
+`dijkstra.cc` (C++17) takes a natural number `n` of edges, 2 positive numbers
+`s` and `e` (starting and ending of path), then `n` pairs of connected vertices
+(both in `1..1023`) and the edge's weight.  The output to stdout is the path
+and the length, e.g.
+
+### Input
+    9 1 6
+    1 2 4
+    1 3 2
+    2 3 1
+    2 4 5
+    3 5 10
+    3 4 8
+    4 5 2
+    4 6 6
+    5 6 3'
+
+### Output
+    1 3 2 4 5 6 (length of 13)
+
+## Problem 5
+`connected.cc` (C++17) takes a natural number `n` and `n` pairs of connected
+vertices from stdin and print the number of connected components of the given
+undirected graph to stdout, e.g.
+
+### Input
+    3
+    1 2
+    3 4
+    4 5
+
+### Output
+    2
diff --git a/usth/MATH2.3/2/[Ch_GraphTheory]_Practical.pdf b/usth/MATH2.3/2/[Ch_GraphTheory]_Practical.pdf
new file mode 100644
index 0000000..3ac3407
--- /dev/null
+++ b/usth/MATH2.3/2/[Ch_GraphTheory]_Practical.pdf
Binary files differdiff --git a/usth/MATH2.3/2/adjmat2edges.cc b/usth/MATH2.3/2/adjmat2edges.cc
new file mode 100644
index 0000000..d9cf14f
--- /dev/null
+++ b/usth/MATH2.3/2/adjmat2edges.cc
@@ -0,0 +1,18 @@
+#include <iostream>
+
+using namespace std;
+
+int
+main ()
+{
+  size_t n;
+  int b;
+  cin >> n;
+  for (size_t i = 0; i < n; ++i)
+    for (size_t j = 0; j < n; ++j)
+      {
+        cin >> b;
+        if (i <= j && b > 0)
+          cout << i << " " << j << " " << b << endl;
+      }
+}
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;
+}
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;
+}
diff --git a/usth/MATH2.3/2/dijkstra.cc b/usth/MATH2.3/2/dijkstra.cc
new file mode 100644
index 0000000..e8a7931
--- /dev/null
+++ b/usth/MATH2.3/2/dijkstra.cc
@@ -0,0 +1,55 @@
+#include <iostream>
+#include <deque>
+#include <queue>
+#include <unordered_map>
+#include <vector>
+
+#define ENCODE(w, c, p) (((w) << 20) + ((c) << 10) + (p))
+#define WEIGHT(x) ((x) >> 20)
+#define CUR(x) ((x) >> 10 & 1023)
+#define PREV(x) ((x) & 1023)
+
+using namespace std;
+
+int
+main ()
+{
+  size_t n, a, b, w, s, e;
+  unordered_map<size_t, unordered_map<size_t, size_t>> edges;
+
+  cin >> n >> s >> e;
+  for (size_t i = 0; i < n; ++i)
+    {
+      cin >> a >> b >> w;
+      edges[a][b] = edges[b][a] = w;
+    }
+
+  unordered_map<size_t, size_t> prev;
+  priority_queue<size_t, vector<size_t>, greater<size_t>> pq;
+  pq.push (ENCODE (0, s, s));
+
+  while (!pq.empty ())
+    {
+      size_t p = pq.top ();
+      a = PREV (p);
+      b = CUR (p);
+      w = WEIGHT (p);
+      if (!prev[b])
+        prev[b] = a;
+      if (b == e)
+        break;
+      pq.pop ();
+
+      for (auto const& [i, v] : edges[b])
+        if (!prev[i])
+          pq.push (ENCODE (w + v, i, b));
+    }
+
+  deque<size_t> d;
+  for (; e != s; e = prev[e])
+    d.push_front (e);
+  d.push_front (e);
+  for (auto const& i : d)
+    cout << i << " ";
+  cout << "(length of " << w << ")" << endl;
+}
diff --git a/usth/MATH2.3/2/incidentmat2edges.cc b/usth/MATH2.3/2/incidentmat2edges.cc
new file mode 100644
index 0000000..2fe5d79
--- /dev/null
+++ b/usth/MATH2.3/2/incidentmat2edges.cc
@@ -0,0 +1,33 @@
+#include <iostream>
+#include <map>
+#include <utility>
+
+using namespace std;
+
+int
+main ()
+{
+  int v, e, b;
+  map<pair<int, int>, int> m;
+
+  cin >> v >> e;
+  for (int i = 0; i < v; ++i)
+    {
+      pair<int, int> p {-1, -1};
+
+      for (int j = 0; j < e; ++j)
+        {
+          cin >> b;
+          if (!b)
+            continue;
+          if (p.first < 0)
+            p.first = p.second = j;
+          else
+            p.second = j;
+        }
+      m[p]++;
+    }
+
+  for (auto const& [p, c] : m)
+    cout << p.first << " " << p.second << " " << c << endl;
+}