test/graph/max-clique/yosupo-Maximum-Independent-Set.test.cpp

• View this file on GitHub
• Last update: 2023-05-29 14:59:47+08:00
• Problem: https://judge.yosupo.jp/problem/maximum_independent_set

Depends on

• library/graph/max-clique.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/maximum_independent_set"

#include <iostream>

#include <vector>

#include "../../../library/graph/max-clique.hpp"

using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<vector<bool>> g(n, vector<bool>(n));
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		g[u][v] = g[v][u] = true;
	}
	max_clique<40> solver(n);
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			if(!g[i][j]) {
				solver.add_edge(i, j);
			}
		}
	}
	auto ans = solver.solve();
	cout << ans.size() << "\n";
	for(auto x : ans) {
		cout << x << " \n"[x == ans.back()];
	}
	return 0;
}

#line 1 "test/graph/max-clique/yosupo-Maximum-Independent-Set.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/maximum_independent_set"

#include <iostream>

#include <vector>

#line 3 "library/graph/max-clique.hpp"
#include <bitset>

#include <algorithm>

#include <cassert>


namespace felix {

template<int V>
struct max_clique {
	using B = std::bitset<V>;

	max_clique() : n(0) {}
	explicit max_clique(int _n) : n(_n), g(_n), col_buf(_n) {}

	struct P {
		int idx, col, deg;
		P(int a, int b, int c) : idx(a), col(b), deg(c) {}
	};

	void add_edge(int u, int v) {
		assert(0 <= u && u < n);
		assert(0 <= v && v < n);
		assert(u != v);
		g[u][v] = g[v][u] = 1;
	}

	std::vector<int> solve() {
		std::vector<P> remark;
		for(int i = 0; i < n; i++) {
			remark.emplace_back(i, -1, (int) g[i].size());
		}
		dfs(remark);
		return clique;
	}

private:
	int n;
	std::vector<B> g, col_buf;
	std::vector<int> now, clique;

	void dfs(std::vector<P>& remark) {
		if(clique.size() < now.size()) {
			clique = now;
		}
		std::sort(remark.begin(), remark.end(), [](P a, P b) {
			return a.deg > b.deg;
		});
		int max_c = 1;
		for(auto& p : remark) {
			p.col = 0;
			while((g[p.idx] & col_buf[p.col]).any()) {
				p.col++;
			}
			max_c = std::max(max_c, p.idx + 1);
			col_buf[p.col][p.idx] = 1;
		}
		for(int i = 0; i < max_c; i++) {
			col_buf[i].reset();
		}
		std::sort(remark.begin(), remark.end(), [](P a, P b) {
			return a.col < b.col;
		});
		while(!remark.empty()) {
			auto& p = remark.back();
			if(now.size() + p.col + 1 <= clique.size()) {
				break;
			}
			std::vector<P> new_remark;
			B bs;
			for(auto& q : remark) {
				if(g[p.idx][q.idx]) {
					new_remark.emplace_back(q.idx, -1, 0);
					bs[q.idx] = 1;
				}
			}
			for(auto& q : new_remark) {
				q.deg = (bs & g[q.idx]).count();
			}
			now.emplace_back(p.idx);
			dfs(new_remark);
			now.pop_back();
			remark.pop_back();
		}
	}
};

} // namespace felix

#line 6 "test/graph/max-clique/yosupo-Maximum-Independent-Set.test.cpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<vector<bool>> g(n, vector<bool>(n));
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		g[u][v] = g[v][u] = true;
	}
	max_clique<40> solver(n);
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			if(!g[i][j]) {
				solver.add_edge(i, j);
			}
		}
	}
	auto ans = solver.solve();
	cout << ans.size() << "\n";
	for(auto x : ans) {
		cout << x << " \n"[x == ans.back()];
	}
	return 0;
}

Back to top page