verify/maximum_independent_set.test.cpp

View this file on GitHub
Last update: 2024-12-28 00:04:13+09:00
Problem: https://judge.yosupo.jp/problem/maximum_independent_set

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/maximum_independent_set"
#include "../Utility/template.hpp"
#include "../Algorithm/maximum_independent_set.hpp"

int main() {
    int n, m;
    cin >> n >> m;
    vec<vec<int>> ng(n, vec<int>(n, 0));
    rep(i, 0, m) {
        int u, v;
        cin >> u >> v;
        ng[u][v] = 1;
        ng[v][u] = 1;
    }

    auto res = maximum_independent_set(ng);
    cout << res.size() << endl;
    for(int x : res) cout << x << " ";
    cout << endl;

}

#line 1 "verify/maximum_independent_set.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/maximum_independent_set"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Algorithm/maximum_independent_set.hpp"
vec<int> maximum_independent_set(vec<vec<int>> &ngs) {
	int n = ngs.size();

	int sl = n/2;
	int sr = n - sl;

	vec<ll> ng(n, 0);
	rep(i, 0, n) rep(j, 0, n) if(ngs[i][j]) {
		ng[i] |= 1LL << j;
	}

	vec<int> dp,pre,self,dp2,pre2,self2;
	dp = pre = self = vec<int>(1LL << sl, 0);
	dp2 = pre2 = self2 = vec<int>(1LL << sr, 0);
	self = vec<int>(1LL << sl, -1);
	self2 = vec<int>(1LL << sr, -1);

	rep(s, 1, 1LL << sl) {
		rep(i, 0, sl) if(s >> i & 1) {
			ll ns = s ^ (1LL << i);
			if(chmax(dp[s], dp[ns])) {
				pre[s] = ns;
				self[s] = -1;
			}
			ns = ns & (ns ^ ng[i]);
			if(chmax(dp[s], dp[ns] + 1)) {
				pre[s] = ns;
				self[s] = i;
			}
		}
	}

	rep(s, 1, 1LL << sr) {
		rep(i, 0, sr) if(s >> i & 1) {
			ll ns = s ^ (1LL << i);
			if(chmax(dp2[s], dp2[ns])) {
				pre2[s] = ns;
				self2[s] = -1;
			}
			ns = ns & (ns ^ (ng[i + sl] >> sl));
			if(chmax(dp2[s], dp2[ns] + 1)) {
				pre2[s] = ns;
				self2[s] = i + sl;
			}
		}
	}
     
	int sz = -1;
	vec<ll> id(2, 0);
	vec<int> res;
	rep(s, 0, 1LL << sl) {
		ll out = 0;
		rep(i, 0, sl) if(s >> i & 1) out |= ng[i];
		ll ns = (((1LL << n) - 1) ^ out) >> sl;
		if(chmax(sz, dp[s] + dp2[ns])) {
			id[0] = s;
			id[1] = ns;
		}
	}

	while(id[0] != 0) {
		if(self[id[0]] != -1) res.push_back(self[id[0]]);
		id[0] = pre[id[0]];
	}

	while(id[1] != 0) {
		if(self2[id[1]] != -1) res.push_back(self2[id[1]]);
		id[1] = pre2[id[1]];
	}
	return res;
}

/*
@brief 最大独立集合
*/
#line 4 "verify/maximum_independent_set.test.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    vec<vec<int>> ng(n, vec<int>(n, 0));
    rep(i, 0, m) {
        int u, v;
        cin >> u >> v;
        ng[u][v] = 1;
        ng[v][u] = 1;
    }

    auto res = maximum_independent_set(ng);
    cout << res.size() << endl;
    for(int x : res) cout << x << " ";
    cout << endl;

}