#include "graph_tree/maximum_independent_set.hpp"
#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; }