This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
#define PROBLEM "https://judge.yosupo.jp/problem/maximum_independent_set" #include <bits/stdc++.h> using namespace std; #include "../MaxClique.h" bool edge[44][44]; #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; REP(i,m) { int u, v; cin >> u >> v; edge[u][v] = edge[v][u] = 1; } MaxClique g(n); REP(i,n) REP(j,n) if (!edge[i][j] && i != j) { g.addEdge(i, j); } auto res = g.solve(); cout << res.size() << endl; for (int x : res) { cout << x << ' '; } cout << endl; return 0; }
#line 1 "Graph/tests/clique_maxindependentset.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/maximum_independent_set" #include <bits/stdc++.h> using namespace std; #line 1 "Graph/MaxClique.h" // MaxClique // Copied from https://judge.yosupo.jp/submission/15825 // // 0-based index // // Tested: // - https://judge.yosupo.jp/problem/maximum_independent_set struct MaxClique { static const int MN = 64; // change to bitset for n > 64 int n, deg[MN]; uint64_t g[MN], ans; vector<pair<int,int>> edges; MaxClique(int _n) : n(_n) { fill(g, g+n, 0ull); fill(deg, deg+n, 0); edges.clear(); } // Add bi-directional edge // 0-based index void addEdge(int u, int v) { edges.emplace_back(u, v); ++deg[u]; ++deg[v]; } vector<int> solve() { vector<int> ord(n); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&] (int u, int v) { return deg[u] < deg[v]; }); vector<int> id(n); for (int i = 0; i < n; i++) id[ord[i]] = i; for (const auto& e : edges) { int u = id[e.first], v = id[e.second]; g[u] |= 1ull << v; g[v] |= 1ull << u; } uint64_t r = 0, p = (1ull << n) - 1; ans = 0; dfs(r, p); vector<int> res; for (int i = 0; i < n; i++) { if ((ans >> i) & 1) res.push_back(ord[i]); } return res; } #define cnt __builtin_popcountll void dfs(uint64_t r, uint64_t p) { if (p == 0) { if (cnt(r) > cnt(ans)) ans = r; return; } if (cnt(r | p) <= cnt(ans)) return; int x = __builtin_ctzll(p & -p); uint64_t c = p; while (c > 0) { x = __builtin_ctzll(c & -c); r |= 1ull << x; dfs(r, p & g[x]); r &= ~(1ull << x); p &= ~(1ull << x); c ^= 1ull << x; } } }; #line 7 "Graph/tests/clique_maxindependentset.test.cpp" bool edge[44][44]; #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; REP(i,m) { int u, v; cin >> u >> v; edge[u][v] = edge[v][u] = 1; } MaxClique g(n); REP(i,n) REP(j,n) if (!edge[i][j] && i != j) { g.addEdge(i, j); } auto res = g.solve(); cout << res.size() << endl; for (int x : res) { cout << x << ' '; } cout << endl; return 0; }