From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 6 Jul 2026 19:08:08 +0200 Subject: Initial commit --- 04_graph_algorithms/a.out | Bin 0 -> 14176 bytes 04_graph_algorithms/building_roads_1666.cpp | 32 ++++++ 04_graph_algorithms/building_teams_1668.cpp | 37 +++++++ 04_graph_algorithms/counting_rooms_1192.cpp | 62 +++++++++++ 04_graph_algorithms/high_score_1673.cpp | 61 +++++++++++ 04_graph_algorithms/labyrinth_1193.cpp | 131 ++++++++++++++++++++++++ 04_graph_algorithms/message_route_1667.cpp | 54 ++++++++++ 04_graph_algorithms/round_trip_1669.cpp | 44 ++++++++ 04_graph_algorithms/shortest_routes_i_1671.cpp | 43 ++++++++ 04_graph_algorithms/shortest_routes_ii_1672.cpp | 30 ++++++ 10 files changed, 494 insertions(+) create mode 100755 04_graph_algorithms/a.out create mode 100644 04_graph_algorithms/building_roads_1666.cpp create mode 100644 04_graph_algorithms/building_teams_1668.cpp create mode 100644 04_graph_algorithms/counting_rooms_1192.cpp create mode 100644 04_graph_algorithms/high_score_1673.cpp create mode 100644 04_graph_algorithms/labyrinth_1193.cpp create mode 100644 04_graph_algorithms/message_route_1667.cpp create mode 100644 04_graph_algorithms/round_trip_1669.cpp create mode 100644 04_graph_algorithms/shortest_routes_i_1671.cpp create mode 100644 04_graph_algorithms/shortest_routes_ii_1672.cpp (limited to '04_graph_algorithms') diff --git a/04_graph_algorithms/a.out b/04_graph_algorithms/a.out new file mode 100755 index 0000000..ae515d4 Binary files /dev/null and b/04_graph_algorithms/a.out differ 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 +#include + +void visit(size_t i, const std::vector>& a, + std::vector& 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> 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 c(n, false); + std::vector 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 +#include + +bool visit(size_t i, int c, const std::vector>& a, + std::vector& 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> 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 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 +#include +#include + +class Tile { +public: + int i; + int j; + std::vector 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 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 +#include +#include +#include + +constexpr long long inf = 999999999999999LL; + +size_t findcycle( + size_t v, + const std::vector>& a, + const std::vector& p +) { + std::vector 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> 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 p(n, n); + std::vector d(n, -inf); + d[0] = 0; + std::vector 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 +#include +#include +#include +#include +#include + +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 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(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 + using Overlay = std::pair>>; + + template + Overlay overlay(T t) const { + auto ov = std::vector>(n, std::vector(m, t)); + return {t, ov}; + } + + template + T at(const Overlay& ov, Pos p) const { + return inb(p) ? ov.second[p.i][p.j] : ov.first; + } + + template + void set(Overlay& 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> 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(inf); + std::queue> 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 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 +#include +#include +#include + +constexpr size_t inf = 1999999999; + +int main() { + size_t n, m; + std::cin >> n >> m; + std::vector> 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 q; + std::vector 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 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 +#include + +std::vector cyc; + +int dfs(const std::vector>& a, + std::vector& 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> 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 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 +#include +#include +#include + +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>> 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 d(n, inf); + std::priority_queue 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 +#include +#include + +constexpr size_t inf{999999999999999ULL}; + +int main() { + size_t n, m, q; + std::cin >> n >> m >> q; + std::vector> 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"; + } +} -- cgit v1.3