Submit Info #3040

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

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.55 MiB
example_01 AC 7 ms 0.63 MiB
max_random_00 AC 7 ms 0.62 MiB
max_random_01 WA 9 ms 0.69 MiB
max_random_02 WA 7 ms 0.68 MiB
max_random_03 WA 8 ms 0.67 MiB
max_random_04 WA 6 ms 0.64 MiB
random_00 WA 8 ms 0.62 MiB
random_01 AC 7 ms 0.68 MiB
random_02 WA 5 ms 0.68 MiB
random_03 AC 5 ms 0.63 MiB
random_04 WA 6 ms 0.55 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 struct maxIndependentSet { ll n, ans; vector<ll> contain_for_ans; vector<vector<ll>> g; ll dfs(ll v, vector<ll> &used, vector<ll> &contain) { if(v == n) return 0; ll ret = 0; if(!used[v]) { vector<ll> nv(1, v); for(ll i: g[v]) if(!used[i]) nv.push_back(i); for(ll i: nv) used[i] = 1; contain[v] = 1; ll tmp = dfs(v+1, used, contain)+1; if(ans < tmp) { ans = tmp; contain_for_ans = contain; } contain[v] = 0; for(ll i: nv) used[i] = 0; } ll d = 0; for(ll i: g[v]) if(!used[i]) d++; if(d > 1 || used[v]) { if(!used[v]) { used[v] = 1; ll tmp = dfs(v+1, used, contain); if(ans < tmp) { ans = tmp; contain_for_ans = contain; } used[v] = 0; } else { ll tmp = dfs(v+1, used, contain); if(ans < tmp) { ans = tmp; contain_for_ans = contain; } } } return ret; } maxIndependentSet() {} maxIndependentSet(ll n) : n(n), ans(0), contain_for_ans(n), g(n) {} void add_edge(ll a, ll b) { g[a].push_back(b); g[b].push_back(a); } vector<ll> get() { vector<ll> used(n), contain(n); dfs(0, used, contain); vector<ll> ans_set; REP(i, n) if(contain_for_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; }