10 files changed, 494 insertions, 0 deletions

diff --git a/04_graph_algorithms/a.out b/04_graph_algorithms/a.out
new file mode 100755
index 0000000..ae515d4
--- /dev/null
+++ b/04_graph_algorithms/a.out
diff --git a/04_graph_algorithms/building_roads_1666.cpp b/04_graph_algorithms/building_roads_1666.cpp
new file mode 100644
index 0000000..cf6ac28
--- /dev/null
+++ b/04_graph_algorithms/building_roads_1666.cpp
@@ -0,0 +1,32 @@
+#include <iostream>
+#include <vector>
+
+void visit(size_t i, const std::vector<std::vector<size_t>>& a,
+    std::vector<bool>& c) {
+        if (c[i]) return;
+        c[i] = true;
+        for (auto j : a[i])
+                visit(j, a, c);
+}
+
+int main() {
+        size_t n, m;
+        std::cin >> n >> m;
+        std::vector<std::vector<size_t>> a(n);
+        for (size_t i = 0; i < m; i++) {
+                size_t x, y;
+                std::cin >> x >> y;
+                a[x-1].push_back(y-1);
+                a[y-1].push_back(x-1);
+        }
+
+        std::vector<bool> c(n, false);
+        std::vector<size_t> s;
+        for (size_t i = 0; i < n; i++) {
+                if (c[i]) continue;
+                if (i != 0) s.push_back(i);
+                visit(i, a, c);
+        }
+        std::cout << s.size() << "\n";
+        for (auto x : s) std::cout << "1 " << x+1 << "\n";
+}
diff --git a/04_graph_algorithms/building_teams_1668.cpp b/04_graph_algorithms/building_teams_1668.cpp
new file mode 100644
index 0000000..c98e14d
--- /dev/null
+++ b/04_graph_algorithms/building_teams_1668.cpp
@@ -0,0 +1,37 @@
+#include <iostream>
+#include <vector>
+
+bool visit(size_t i, int c, const std::vector<std::vector<size_t>>& a,
+    std::vector<int>& t) {
+        if (t[i] != 0) return true;
+        t[i] = c;
+        for (auto j : a[i])
+                if (t[j] == c)
+                        return false;
+                else if (!visit(j, 3-c, a, t)) return false;
+        return true;
+}
+
+int main() {
+        size_t n, m;
+        std::cin >> n >> m;
+        std::vector<std::vector<size_t>> a(n);
+        for (size_t i = 0; i < m; i++) {
+                size_t x, y;
+                std::cin >> x >> y;
+                a[x-1].push_back(y-1);
+                a[y-1].push_back(x-1);
+        }
+
+        std::vector<int> t(n);
+        for (size_t i = 0; i < n; i++) {
+                if (t[i] == 0) {
+                        if (!visit(i, 1, a, t)) {
+                                std::cout << "IMPOSSIBLE\n";
+                                return 0;
+                        }
+                }
+        }
+        for (auto x : t) std::cout << x << " ";
+        std::cout << "\n";
+}
diff --git a/04_graph_algorithms/counting_rooms_1192.cpp b/04_graph_algorithms/counting_rooms_1192.cpp
new file mode 100644
index 0000000..dc71529
--- /dev/null
+++ b/04_graph_algorithms/counting_rooms_1192.cpp
@@ -0,0 +1,62 @@
+#include <iostream>
+#include <string>
+#include <vector>
+
+class Tile {
+public:
+        int i;
+        int j;
+        std::vector<Tile> neighbors() const {
+                return {Tile{i-1,j}, Tile{i+1,j}, Tile{i,j-1}, Tile{i,j+1}};
+        }
+};
+
+class Map {
+public:
+        int n;
+        int m;
+
+        Map(int i, int j) : n{i}, m{j}, c(n*m, 0) {}
+        int color(Tile t) const { return inbound(t) ? c[ind(t)] : -1; }
+        void setcolor(Tile t, int k) { if (inbound(t)) c[ind(t)] = k; }
+        bool wall(Tile t) const { return !inbound(t) || c[ind(t)] == -1; }
+        void setwall(Tile t) { if (inbound(t)) setcolor(t, -1); }
+private:
+        std::vector<int> c;
+
+        size_t ind(Tile t) const { return m*t.i + t.j; }
+        bool inbound(Tile t) const {
+                return t.i >= 0 && t.i < n && t.j >= 0 && t.j < m;
+        }
+};
+
+Map readmap() {
+        int n, m;
+        std::string s;
+        std::cin >> n >> m;
+        Map map(n, m);
+        for (int i = 0; i < n; i++) {
+                std::cin >> s;
+                for (int j = 0; j < m; j++)
+                        if (s[j] == '#')
+                                map.setwall(Tile{i, j});
+        }
+        return map;
+}
+
+void visit(Map& m, Tile t, int c) {
+        m.setcolor(t, c);
+        for (auto u : t.neighbors())
+                if (m.color(u) == 0)
+                        visit(m, u, c);
+}
+
+int main() {
+        auto m = readmap();
+        int c{0};
+        for (int i = 0; i < m.n; i++)
+                for (int j = 0; j < m.m; j++)
+                        if (m.color(Tile{i, j}) == 0)
+                                visit(m, Tile{i, j}, ++c);
+        std::cout << c << "\n";
+}
diff --git a/04_graph_algorithms/high_score_1673.cpp b/04_graph_algorithms/high_score_1673.cpp
new file mode 100644
index 0000000..c327ba0
--- /dev/null
+++ b/04_graph_algorithms/high_score_1673.cpp
@@ -0,0 +1,61 @@
+#include <algorithm>
+#include <iostream>
+#include <tuple>
+#include <vector>
+
+constexpr long long inf = 999999999999999LL;
+
+size_t findcycle(
+        size_t v,
+        const std::vector<std::tuple<size_t, size_t, long long>>& a, 
+        const std::vector<size_t>& p
+) {
+        std::vector<bool> visited(p.size(), false);
+        visited[v] = true;
+        size_t u = p[v];
+        while (!visited[u]) {
+                visited[u] = true;
+                u = p[u];
+        }
+        return u;
+}
+
+int main() {
+        size_t n, m;
+        std::cin >> n >> m;
+        std::vector<std::tuple<size_t, size_t, long long>> a(m);
+        for (size_t i = 0; i < m; i++) {
+                size_t x, y;
+                long long w;
+                std::cin >> x >> y >> w;
+                a[i] = {x-1, y-1, w};
+        }
+
+        std::vector<size_t> p(n, n);
+        std::vector<long long> d(n, -inf);
+        d[0] = 0;
+        std::vector<bool> reach_1(n, false), reach_n(n, false);
+        reach_1[0] = reach_n[n-1] = true;
+        for (size_t i = 0; i < n; i++) {
+                for (auto [v, u, w] : a) {
+                        if (d[u] < d[v] + w) {
+                                d[u] = d[v] + w;
+                                p[u] = v;
+                        }
+                        reach_n[v] = reach_n[v] || reach_n[u];
+                        reach_1[u] = reach_1[u] || reach_1[v];
+                }
+        }
+
+        for (auto [v, u, w] : a) {
+                if (d[u] < d[v] + w) {
+                        size_t x = findcycle(u, a, p);
+                        if (reach_1[x] && reach_n[x]) {
+                                std::cout << "-1\n";
+                                return 0;
+                        }
+                }
+        }
+
+        std::cout << d[n-1] << "\n";
+}
diff --git a/04_graph_algorithms/labyrinth_1193.cpp b/04_graph_algorithms/labyrinth_1193.cpp
new file mode 100644
index 0000000..30f8c0b
--- /dev/null
+++ b/04_graph_algorithms/labyrinth_1193.cpp
@@ -0,0 +1,131 @@
+#include <iostream>
+#include <queue>
+#include <ranges>
+#include <string>
+#include <tuple>
+#include <vector>
+
+struct Pos {
+        size_t i;
+        size_t j;
+
+        Pos(size_t a = 0, size_t b = 0) : i{a}, j{b} {}
+        bool operator==(const Pos& p) const { return i == p.i && j == p.j; }
+
+        std::vector<Pos> neighbors() const {
+                return {Pos(i+1, j), Pos(i-1, j), Pos(i, j+1), Pos(i, j-1)};
+        }
+
+        char dir(const Pos& p) const {
+                if (p.i == i+1 && p.j == j) return 'D';
+                if (p.i == i-1 && p.j == j) return 'U';
+                if (p.i == i && p.j == j+1) return 'R';
+                if (p.i == i && p.j == j-1) return 'L';
+                return 'X';
+        }
+};
+ 
+class Map {
+public:
+        Map(size_t i, size_t j) : n{i}, m{j}, v(n, std::vector<bool>(m)) {}
+        Pos start() const { return a; }
+        Pos finish() const { return b; }
+        bool operator[](Pos p) const { return inb(p) && v[p.i][p.j]; }
+
+        friend std::istream& operator>>(std::istream& is, Map& map) {
+                std::string s;
+                is >> s;
+                for (size_t j = 0; j < map.m; j++)
+                        map.readchar(s[j], map.l, j);
+                map.l++;
+                return is;
+        }
+ 
+        friend std::ostream& operator<<(std::ostream& os, const Map& map) {
+                for (size_t i = 0; i < map.n; i++) {
+                        for (size_t j = 0; j < map.m; j++) {
+                                if (map.a == Pos(i, j)) os << 'A';
+                                else if (map.b == Pos(i, j)) os << 'B';
+                                else os << (map.v[i][j] ? '.' : '#');
+                        }
+                        os << "\n";
+                }
+                return os;
+        }
+
+        template<typename T>
+        using Overlay = std::pair<T, std::vector<std::vector<T>>>;
+
+        template<typename T>
+        Overlay<T> overlay(T t) const {
+                auto ov = std::vector<std::vector<T>>(n, std::vector(m, t));
+                return {t, ov};
+        }
+
+        template<typename T>
+        T at(const Overlay<T>& ov, Pos p) const {
+                return inb(p) ? ov.second[p.i][p.j] : ov.first;
+        }
+
+        template<typename T>
+        void set(Overlay<T>& ov, Pos p, T val) const {
+                if (inb(p)) ov.second[p.i][p.j] = val;
+        }
+private:
+        size_t l{0};
+        size_t n;
+        size_t m;
+        Pos a;
+        Pos b;
+        std::vector<std::vector<bool>> v;
+ 
+        void readchar(char c, size_t i, size_t j) {
+                v[i][j] = c != '#';
+                if (c == 'A') a = {i, j};
+                if (c == 'B') b = {i, j};
+        }
+ 
+        bool inb(Pos p) const { return p.i < n && p.j < m; }
+};
+
+int main() {
+        size_t n, m;
+        std::cin >> n >> m;
+        Map map(n, m);
+        for (size_t i = 0; i < n; i++)
+                std::cin >> map;
+
+        constexpr size_t inf{999999999};
+        auto d = map.overlay<size_t>(inf);
+        std::queue<std::pair<Pos, size_t>> q;
+        q.push({map.start(), 0});
+        while (!q.empty()) {
+                auto [p, w] = q.front();
+                q.pop();
+                if (!map[p] || map.at(d, p) != inf) continue;
+                map.set(d, p, w);
+                for (auto x : p.neighbors()) q.push({x, w+1});
+        }
+
+        if (map.at(d, map.finish()) == inf) {
+                std::cout << "NO\n";
+        } else {
+                std::cout << "YES\n" << map.at(d, map.finish()) << "\n";
+
+                // Backtrack
+                Pos p = map.finish(); 
+                std::vector<char> path;
+                do {
+                        for (auto x : p.neighbors()) {
+                                if (map.at(d, x) == map.at(d, p)-1) {
+                                        path.push_back(x.dir(p));
+                                        p = x;
+                                        break;
+                                }
+                        }
+                } while (p != map.start());
+                for (auto c : path | std::views::reverse)
+                        std::cout << c;
+                std::cout << "\n";
+        }
+}
diff --git a/04_graph_algorithms/message_route_1667.cpp b/04_graph_algorithms/message_route_1667.cpp
new file mode 100644
index 0000000..280f7d6
--- /dev/null
+++ b/04_graph_algorithms/message_route_1667.cpp
@@ -0,0 +1,54 @@
+#include <iostream>
+#include <queue>
+#include <ranges>
+#include <vector>
+
+constexpr size_t inf = 1999999999;
+
+int main() {
+        size_t n, m;
+        std::cin >> n >> m;
+        std::vector<std::vector<size_t>> a(n);
+        for (size_t i = 0; i < m; i++) {
+                size_t x, y;
+                std::cin >> x >> y;
+                a[x-1].push_back(y-1);
+                a[y-1].push_back(x-1);
+        }
+
+        std::queue<size_t> q;
+        std::vector<size_t> d(n, inf);
+        d[0] = 0;
+        q.push(0);
+        while (!q.empty()) {
+                auto i = q.front();
+                q.pop();
+                if (i == n-1) break;
+                for (auto j : a[i]) {
+                        if (d[j] > d[i]+1) {
+                                d[j] = d[i] + 1;
+                                q.push(j);
+                        }
+                }
+        }
+
+        if (d[n-1] == inf) {
+                std::cout << "IMPOSSIBLE\n";
+        } else {
+                std::cout << d[n-1]+1 << "\n";
+                // Backtracking
+                std::vector<size_t> v;
+                v.push_back(n-1);
+                while (v.back() != 0) {
+                        for (auto j : a[v.back()]) {
+                                if (d[j] == d[v.back()]-1) {
+                                        v.push_back(j);
+                                        break;
+                                }
+                        }
+                }
+                for (auto x : v | std::views::reverse)
+                        std::cout << x+1 << " ";
+                std::cout << "\n";
+        }
+}
diff --git a/04_graph_algorithms/round_trip_1669.cpp b/04_graph_algorithms/round_trip_1669.cpp
new file mode 100644
index 0000000..c19b29d
--- /dev/null
+++ b/04_graph_algorithms/round_trip_1669.cpp
@@ -0,0 +1,44 @@
+#include <iostream>
+#include <vector>
+
+std::vector<int> cyc;
+
+int dfs(const std::vector<std::vector<int>>& a,
+    std::vector<bool>& v, int i, int p) {
+        v[i] = true;
+        for (auto x : a.at(i)) {
+                if (x == p) continue;
+                if (v.at(x)) {
+                        cyc.push_back(x);
+                        cyc.push_back(i);
+                        return x;
+                }
+                if (int r = dfs(a, v, x, i); r != 0) {
+                        cyc.push_back(i);
+                        if (r == i) {
+                                std::cout << cyc.size() << "\n";
+                                for (auto y : cyc) std::cout << y << " ";
+                                std::cout << "\n";
+                                exit(0);
+                        } else return r;
+                }
+        }
+        return 0;
+}
+
+int main() {
+        int n, m;
+        std::cin >> n >> m;
+        std::vector<std::vector<int>> a(n+1);
+        for (int i = 0; i < m; i++) {
+                int x, y;
+                std::cin >> x >> y;
+                a[x].push_back(y);
+                a[y].push_back(x);
+        }
+        std::vector<bool> v(n+1);
+        for (int i = 1; i <= n; i++)
+                if (!v.at(i))
+                        dfs(a, v, i, 0);
+        std::cout << "IMPOSSIBLE\n";
+}
diff --git a/04_graph_algorithms/shortest_routes_i_1671.cpp b/04_graph_algorithms/shortest_routes_i_1671.cpp
new file mode 100644
index 0000000..89f675d
--- /dev/null
+++ b/04_graph_algorithms/shortest_routes_i_1671.cpp
@@ -0,0 +1,43 @@
+#include <iostream>
+#include <queue>
+#include <utility>
+#include <vector>
+
+class dvpair {
+public:
+        size_t d;
+        size_t v;
+        auto operator<=>(const dvpair& p) const { return p.d <=> d; }
+};
+
+int main() {
+        size_t n, m;
+        std::cin >> n >> m;
+        std::vector<std::vector<std::pair<size_t, size_t>>> a(n);
+        for (size_t i = 0; i < m; i++) {
+                size_t x, y, z;
+                std::cin >> x >> y >> z;
+                a[x-1].push_back({y-1, z});
+        }
+
+        constexpr size_t inf{999999999999999ULL};
+        std::vector<size_t> d(n, inf);
+        std::priority_queue<dvpair> q;
+        d[0] = 0;
+        q.push({0, 0});
+        while (!q.empty()) {
+                auto [dd, p] = q.top();
+                q.pop();
+                if (dd > d[p])
+                        continue;
+                for (auto [r, w] : a[p]) {
+                        if (w + d[p] < d[r]) {
+                                d[r] = d[p] + w;
+                                q.push({d[r], r});
+                        }
+                }
+        }
+        for (auto x : d)
+                std::cout << x << " ";
+        std::cout << "\n";
+}
diff --git a/04_graph_algorithms/shortest_routes_ii_1672.cpp b/04_graph_algorithms/shortest_routes_ii_1672.cpp
new file mode 100644
index 0000000..d49cb71
--- /dev/null
+++ b/04_graph_algorithms/shortest_routes_ii_1672.cpp
@@ -0,0 +1,30 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+constexpr size_t inf{999999999999999ULL};
+
+int main() {
+        size_t n, m, q;
+        std::cin >> n >> m >> q;
+        std::vector<std::vector<size_t>> d(n, std::vector(n, inf));
+        for (size_t i = 0; i < n; i++) d[i][i] = 0;
+        for (size_t i = 0; i < m; i++) {
+                size_t x, y, z;
+                std::cin >> x >> y >> z;
+                d[x-1][y-1] = d[y-1][x-1] = std::min(d[x-1][y-1], z);
+        }
+
+        for (size_t k = 0; k < n; k++)
+                for (size_t i = 0; i < n; i++)
+                        for (size_t j = 0; j < n; j++)
+                                d[j][i] = d[i][j] =
+                                    std::min(d[i][j], d[i][k] + d[k][j]);
+
+        for (size_t i = 0; i < q; i++) {
+                size_t x, y;
+                std::cin >> x >> y;
+                long long int dd = d[x-1][y-1];
+                std::cout << (dd == inf ? -1LL : dd) << "\n";
+        }
+}