:heavy_check_mark: 最大独立集合(V<=50)
(graph_tree/maximum_independent_set.hpp)

Depends on

Verified with

Code

#pragma once
#include<tuple>
#include<vector>
#include<bitset>
#include"graph_template.hpp"

/**
 * @brief 最大独立集合(V<=50)
 */

std::pair<int,std::bitset<50>> __maximum_independent_set(std::vector<std::bitset<50>>v,std::bitset<50>b=std::bitset<50>()){
	int n=v.size();
	auto del=[&](int k){
		for(int i=0;i<n;++i){
			v[k][i]=0;
			v[i][k]=0;
		}
		b[k]=1;
	};
	int t=-1;
	for(int i=0;i<n;++i)if(b[i]==0)t=i;
	if(t==-1)return std::make_pair(0,std::bitset<50>());
	if(v[t].count()<=1){
		for(int i=0;i<n;++i)if(v[t][i])del(i);
		del(t);
		auto p=__maximum_independent_set(v,b);
		p.first++;
		p.second[t]=1;
		return p;
	}else{
		std::vector<int>tmp;
		for(int i=0;i<n;++i)if(v[t][i])tmp.push_back(i);
		del(t);
		auto p=__maximum_independent_set(v,b);
		for(auto e:tmp)del(e);
		auto q=__maximum_independent_set(v,b);
		q.first++;
		q.second[t]=1;
		return p.first>q.first?p:q;
	}
}

std::vector<int> maximum_independent_set(const graph& g){
	std::vector<std::bitset<50>>v(g.size());
	for(size_t i=0;i<g.size();++i){
		for(auto e:g[i]){
			v[i][e]=1;
		}
	}
	auto res=__maximum_independent_set(v);
	std::vector<int>ret;
	for(size_t i=0;i<res.second.size();++i){
		if(res.second[i])ret.push_back(i);
	}
	return ret;
}
#line 2 "graph_tree/maximum_independent_set.hpp"
#include<tuple>
#include<vector>
#include<bitset>
#line 4 "graph_tree/graph_template.hpp"
#include<iostream>
/**
 * @brief グラフテンプレート
 */

using graph=std::vector<std::vector<int>>;
template<typename T>
using graph_w=std::vector<std::vector<std::pair<int,T>>>;

graph load_graph(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;}
graph load_digraph(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);}return g;}
graph load_graph0(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;}
graph load_digraph0(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);}return g;}
graph load_tree(int n){graph g(n);for(int i=0;i<n-1;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;}
graph load_tree0(int n){graph g(n);for(int i=0;i<n-1;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;}
graph load_treep(int n){graph g(n);for(int i=0;i<n-1;++i){int t;std::cin>>t;g[i+1].push_back(t);g[t].push_back(i+1);}return g;}
template<typename T>graph_w<T> load_graph_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;}
template<typename T>graph_w<T> load_digraph_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);}return g;}
template<typename T>graph_w<T> load_graph0_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;}
template<typename T>graph_w<T> load_digraph0_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);}return g;}
template<typename T>graph_w<T> load_tree_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;}
template<typename T>graph_w<T> load_tree0_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;}
template<typename T>graph_w<T> load_treep_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int t;T u;std::cin>>t>>u;g[i+1].emplace_back(t,u);g[t].emplace_back(i+1,u);}return g;}
#line 6 "graph_tree/maximum_independent_set.hpp"

/**
 * @brief 最大独立集合(V<=50)
 */

std::pair<int,std::bitset<50>> __maximum_independent_set(std::vector<std::bitset<50>>v,std::bitset<50>b=std::bitset<50>()){
	int n=v.size();
	auto del=[&](int k){
		for(int i=0;i<n;++i){
			v[k][i]=0;
			v[i][k]=0;
		}
		b[k]=1;
	};
	int t=-1;
	for(int i=0;i<n;++i)if(b[i]==0)t=i;
	if(t==-1)return std::make_pair(0,std::bitset<50>());
	if(v[t].count()<=1){
		for(int i=0;i<n;++i)if(v[t][i])del(i);
		del(t);
		auto p=__maximum_independent_set(v,b);
		p.first++;
		p.second[t]=1;
		return p;
	}else{
		std::vector<int>tmp;
		for(int i=0;i<n;++i)if(v[t][i])tmp.push_back(i);
		del(t);
		auto p=__maximum_independent_set(v,b);
		for(auto e:tmp)del(e);
		auto q=__maximum_independent_set(v,b);
		q.first++;
		q.second[t]=1;
		return p.first>q.first?p:q;
	}
}

std::vector<int> maximum_independent_set(const graph& g){
	std::vector<std::bitset<50>>v(g.size());
	for(size_t i=0;i<g.size();++i){
		for(auto e:g[i]){
			v[i][e]=1;
		}
	}
	auto res=__maximum_independent_set(v);
	std::vector<int>ret;
	for(size_t i=0;i<res.second.size();++i){
		if(res.second[i])ret.push_back(i);
	}
	return ret;
}
Back to top page