sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM \ "https://judge.yosupo.jp/problem/chordal_graph_recognition.test.cpp" #include "../../graph/chordal_graph_recognition.hpp" #include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i) #define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i) #define all(x) begin(x), end(x) template <typename T> bool chmax(T& a, const T& b) { return a < b ? (a = b, 1) : 0; } template <typename T> bool chmin(T& a, const T& b) { return a > b ? (a = b, 1) : 0; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); int N, M; cin >> N >> M; vector<vector<int>> G(N); rep(i, 0, M) { int a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } auto [ans, vec] = recognize_chordal_graph(G); cout << (ans ? "YES" : "NO") << "\n"; if (!ans) cout << vec.size() << "\n"; for (int i = 0; i < (int)vec.size(); ++i) { cout << vec[i] << (i < (int)vec.size() - 1 ? " " : "\n"); } }
#line 1 "test/yosupo/chordal_graph_recognition.test.cpp" #define PROBLEM \ "https://judge.yosupo.jp/problem/chordal_graph_recognition.test.cpp" #line 2 "graph/chordal_graph_recognition.hpp" #include <algorithm> #include <cassert> #include <queue> #include <set> #include <utility> #include <vector> #line 4 "graph/lex_bfs.hpp" #line 4 "data-structure/partition_refinement.hpp" #include <map> #line 7 "data-structure/partition_refinement.hpp" class PartitionRefinement { public: PartitionRefinement() = default; explicit PartitionRefinement(int n) : sets(1), cls(n, 0) { for (int i = 0; i < n; ++i) sets[0].insert(i); } int find(int x) const { return cls[x]; } bool same(int x, int y) const { int cx = find(x), cy = find(y); return cx != -1 && cy != -1 && cx == cy; } bool contains(int x) const { return cls[x] != -1; } void erase(int x) { if (contains(x)) { sets[cls[x]].erase(x); cls[x] = -1; } } int size(int i) const { return sets[i].size(); } int member(int i) const { assert(0 <= i && i < (int)sets.size()); return *sets[i].begin(); } std::vector<int> members(int i) const { assert(0 <= i && i < (int)sets.size()); return std::vector<int>(sets[i].begin(), sets[i].end()); } std::vector<std::pair<int, int>> refine(const std::vector<int>& pivot) { std::map<int, std::vector<int>> split; for (auto x : pivot) { if (!contains(x)) continue; int i = cls[x]; split[i].push_back(x); sets[i].erase(x); } std::vector<std::pair<int, int>> updated; for (auto& [i, s] : split) { int ni = sets.size(); sets.emplace_back(s.begin(), s.end()); if (sets[i].size() < sets[ni].size()) { std::swap(sets[i], sets[ni]); } if (sets[ni].empty()) { sets.pop_back(); continue; } for (auto x : sets[ni]) { cls[x] = ni; } updated.push_back({i, ni}); } return updated; } private: std::vector<std::set<int>> sets; std::vector<int> cls; }; #line 6 "graph/lex_bfs.hpp" std::vector<int> lex_bfs(const std::vector<std::vector<int>>& G) { const int n = G.size(); PartitionRefinement pr(n); std::vector<int> prv(1, -1), nxt(1, -1); std::vector<int> ord; int k = 0; for (int i = 0; i < n; ++i) { while (pr.size(k) == 0) { k = nxt[k]; } int x = pr.member(k); ord.push_back(x); pr.erase(x); std::vector<int> pivot; std::set<int> neighbor; for (int y : G[x]) { if (pr.contains(y)) { pivot.push_back(y); neighbor.insert(y); } } for (auto [s, t] : pr.refine(pivot)) { if ((int)prv.size() <= t) { prv.resize(t + 1, -1); nxt.resize(t + 1, -1); } if (neighbor.contains(pr.member(s))) { if (nxt[s] >= 0) prv[nxt[s]] = t; nxt[t] = nxt[s]; prv[t] = s; nxt[s] = t; } else { if (prv[s] >= 0) nxt[prv[s]] = t; prv[t] = prv[s]; prv[s] = t; nxt[t] = s; } } if (prv[k] != -1) k = prv[k]; } return ord; } #line 10 "graph/chordal_graph_recognition.hpp" // if G is chordal, return a perfect elimination ordering // otherwise return an induced cycle of length >= 4 std::pair<bool, std::vector<int>> recognize_chordal_graph( const std::vector<std::vector<int>>& G) { const int n = G.size(); std::vector<std::set<int>> st(n); for (int x = 0; x < n; ++x) { for (int y : G[x]) st[x].insert(y); } auto ord = lex_bfs(G); std::ranges::reverse(ord); std::vector<int> idx(n, -1); for (int x = 0; x < n; ++x) idx[ord[x]] = x; // check if ord is a perfect elimination ordering for (int i = n - 1; i >= 0; --i) { int x = ord[i]; // find the first neighbor z of x that appears after x std::pair<int, int> neighbor(n, -1); for (int y : G[x]) { if (idx[y] > i) { neighbor = std::min(neighbor, {idx[y], y}); } } auto [j, z] = neighbor; if (j == n) continue; // check if N(x) - z is a subset of N(z) for (int y : G[x]) { if (idx[y] > i && y != z && !st[y].count(z)) { // not chordal // bfs from y to z using vertices after x and not in N(x) std::queue<int> que; que.push(y); std::vector<int> prv(n, -1); prv[y] = y; prv[z] = -1; for (int v : G[x]) { if (v != y && v != z) { prv[v] = -2; } } while (!que.empty()) { int v = que.front(); que.pop(); for (int u : G[v]) { if (idx[u] > i && prv[u] == -1) { prv[u] = v; que.push(u); } } } assert(prv[z] != -1); std::vector<int> cycle; int v = z; while (prv[v] != v) { cycle.push_back(v); v = prv[v]; } cycle.push_back(y); cycle.push_back(x); return {false, cycle}; } } } return {true, ord}; } #line 5 "test/yosupo/chordal_graph_recognition.test.cpp" #include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i) #define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i) #define all(x) begin(x), end(x) template <typename T> bool chmax(T& a, const T& b) { return a < b ? (a = b, 1) : 0; } template <typename T> bool chmin(T& a, const T& b) { return a > b ? (a = b, 1) : 0; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); int N, M; cin >> N >> M; vector<vector<int>> G(N); rep(i, 0, M) { int a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } auto [ans, vec] = recognize_chordal_graph(G); cout << (ans ? "YES" : "NO") << "\n"; if (!ans) cout << vec.size() << "\n"; for (int i = 0; i < (int)vec.size(); ++i) { cout << vec[i] << (i < (int)vec.size() - 1 ? " " : "\n"); } }