Submit Info #3041

Problem Lang User Status Time Memory
Maximum Independent Set cpp (anonymous) WA 8 ms 0.68 MiB

ケース詳細
Name Status Time Memory
example_00 AC 7 ms 0.62 MiB
example_01 AC 6 ms 0.61 MiB
max_random_00 AC 7 ms 0.68 MiB
max_random_01 WA 6 ms 0.67 MiB
max_random_02 WA 6 ms 0.63 MiB
max_random_03 WA 8 ms 0.63 MiB
max_random_04 WA 7 ms 0.64 MiB
random_00 WA 7 ms 0.68 MiB
random_01 AC 5 ms 0.68 MiB
random_02 AC 5 ms 0.62 MiB
random_03 AC 5 ms 0.63 MiB
random_04 WA 7 ms 0.61 MiB

#include <bits/stdc++.h> using namespace std; using ll = long long; using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> void chmin(T &a, const T &b) { a = min(a, b); } template<typename T> void chmax(T &a, const T &b) { a = max(a, b); } struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio; #ifdef DEBUG_ #include "../program_contest_library/memo/dump.hpp" #else #define dump(...) #endif const ll INF = 1LL<<60; // O(n*1.466^n) n<=40で16ms class maxIndependentSet { public: int n; vector<int> deg, used, dead, ans; vector<vector<int>> g; private: int ret, cnt, alive; void dfs() { if(cnt+alive <= ret) return; int v = -1; REP(i, n) if(!used[i] && !dead[i]) { if(deg[i] <= 1) { v = i; break; } if(v<0 || deg[v]<deg[i]) v=i; } if(v<0) return; if(deg[v] != 1) { dead[v] = 1; alive--; for(auto i: g[v]) deg[i]--; dfs(); dead[v] = 0; alive++; for(auto i: g[v]) deg[i]++; } { used[v] = 1; alive--; for(auto i: g[v]) if(dead[i] == 0) { dead[i]++; alive -= !used[i]; } cnt++; if(ret < cnt) ans = used, ret = cnt; dfs(); used[v] = 0; alive++; for(auto i: g[v]) { dead[i]--; if(dead[i] == 0) alive += !used[i]; } cnt--; } } public: maxIndependentSet() {} maxIndependentSet(ll n) : n(n), deg(n), used(n), dead(n), ans(n), g(n) {} void add_edge(ll a, ll b) { g[a].push_back(b); g[b].push_back(a); } vector<ll> get() { REP(i, n) deg[i] = g[i].size(); ret = cnt = 0, alive = n; dfs(); vector<ll> ans_set; REP(i, n) if(ans[i]) ans_set.push_back(i); return ans_set; } }; int main() { ll n, m; cin >> n >> m; maxIndependentSet graph(n); REP(i, m) { ll u, v; cin >> u >> v; graph.add_edge(u, v); } auto ans = graph.get(); cout << ans.size() << "\n"; REP(i, ans.size()) cout << ans[i] << (i+1==(ll)ans.size() ? "\n" : " "); cout << flush; }