sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/maximum_independent_set" #include "../../graph/maximum_independent_set.hpp" #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<vector<int>> G(N); for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } auto ans = maximum_independent_set(G); cout << ans.size() << endl; for (int i = 0; i < ans.size(); ++i) cout << ans[i] << (i < ans.size() - 1 ? " " : "\n"); }
#line 1 "test/yosupo/maximum_independent_set.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/maximum_independent_set" #line 2 "graph/maximum_independent_set.hpp" #include <algorithm> #include <vector> std::vector<int> maximum_independent_set( const std::vector<std::vector<int>>& G) { const int n = G.size(); std::vector<bool> used(n), ans(n); std::vector<int> deg(n), dead(n); std::ranges::transform(G, deg.begin(), [&](auto& g) { return g.size(); }); int res = 0, cnt = 0, alive = n; auto dfs = [&](const auto& dfs) { if (cnt + alive <= res) return; int v = -1; for (int i = 0; i < n; ++i) { if (used[i] || dead[i]) continue; if (deg[i] <= 1) { v = i; break; } if (v < 0 || deg[v] < deg[i]) v = i; } if (v < 0) return; // not use if (deg[v] != 1) { dead[v] = true; --alive; for (int u : G[v]) --deg[u]; dfs(dfs); dead[v] = false; ++alive; for (int u : G[v]) ++deg[u]; } // use used[v] = true; --alive; for (int u : G[v]) { if (!dead[u]) --alive; ++dead[u]; } ++cnt; if (res < cnt) { ans = used; res = cnt; } dfs(dfs); used[v] = false; ++alive; for (int u : G[v]) { --dead[u]; if (!dead[u]) ++alive; } --cnt; }; dfs(dfs); std::vector<int> ret; for (int i = 0; i < n; ++i) { if (ans[i]) ret.push_back(i); } return ret; } #line 4 "test/yosupo/maximum_independent_set.test.cpp" #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<vector<int>> G(N); for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } auto ans = maximum_independent_set(G); cout << ans.size() << endl; for (int i = 0; i < ans.size(); ++i) cout << ans[i] << (i < ans.size() - 1 ? " " : "\n"); }