From a3dd2581ed4847670f81157091016c14ca18803d Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Tue, 14 Jan 2020 18:29:11 +0700 Subject: [usth/MATH2.3] Mathemate Discretely --- usth/MATH2.3/2/README.md | 59 ++++++++++++++++++++++++++ usth/MATH2.3/2/[Ch_GraphTheory]_Practical.pdf | Bin 0 -> 30323 bytes usth/MATH2.3/2/adjmat2edges.cc | 18 ++++++++ usth/MATH2.3/2/bipartite.cc | 55 ++++++++++++++++++++++++ usth/MATH2.3/2/connected.cc | 44 +++++++++++++++++++ usth/MATH2.3/2/dijkstra.cc | 55 ++++++++++++++++++++++++ usth/MATH2.3/2/incidentmat2edges.cc | 33 ++++++++++++++ 7 files changed, 264 insertions(+) create mode 100644 usth/MATH2.3/2/README.md create mode 100644 usth/MATH2.3/2/[Ch_GraphTheory]_Practical.pdf create mode 100644 usth/MATH2.3/2/adjmat2edges.cc create mode 100644 usth/MATH2.3/2/bipartite.cc create mode 100644 usth/MATH2.3/2/connected.cc create mode 100644 usth/MATH2.3/2/dijkstra.cc create mode 100644 usth/MATH2.3/2/incidentmat2edges.cc (limited to 'usth/MATH2.3/2') 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 Binary files /dev/null and b/usth/MATH2.3/2/[Ch_GraphTheory]_Practical.pdf differ diff --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 + +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 +#include +#include +#include + +using namespace std; + +int +main () +{ + unordered_map> adj; + size_t n, u, v; + cin >> n; + while (n--) + { + cin >> u >> v; + adj[u][v]++; + adj[v][u]++; + } + + queue q; + set 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 +#include +#include +#include + +using namespace std; + +int +main () +{ + size_t n, a, b; + unordered_map> edges; + + cin >> n; + for (size_t i = 0; i < n; ++i) + { + cin >> a >> b; + edges[a].insert (b); + edges[b].insert (a); + } + + unordered_set s; + size_t count = 0; + for (auto const& [v, p] : edges) + { + if (s.count (v)) + continue; + count++; + vector 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 +#include +#include +#include +#include + +#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> 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 prev; + priority_queue, greater> 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 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 +#include +#include + +using namespace std; + +int +main () +{ + int v, e, b; + map, int> m; + + cin >> v >> e; + for (int i = 0; i < v; ++i) + { + pair 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; +} -- cgit 1.4.1