src/test/yosupo_maximum_independent_set.cpp

• View this file on GitHub
• Last update: 2025-10-08 00:44:44+09:00
• Problem: https://judge.yosupo.jp/problem/maximum_independent_set

Depends on

• src/maximal_independent_set.hpp
• src/template.hpp

Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,M;
    cin>>N>>M;
    vector<BS> G(N);
    rep(i,M){
        int u,v;
        cin>>u>>v;
        G[u][v]=G[v][u]=1;
    }
    BS ret=maximal_independent_set(G);
    cout<<ret.count()<<"\n";
    rep(i,N) if(ret[i]) cout<<i<<" ";
    cout<<"\n";
}

#line 1 "src/test/yosupo_maximum_independent_set.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/maximum_independent_set"
#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 2 "src/maximal_independent_set.hpp"

using BS = bitset<40>;
BS maximal_independent_set(vector<BS> g, BS d = 0) {
    int n = si(g);
    BS ret = 0;
    int v = -1;
    rep(i, n) if(!d[i]) v = i;
    if(v == -1) return ret;

    d[v] = 1;
    rep(i, n) g[i][v] = 0;
    if(g[v].count() > 1) {
        BS vs = maximal_independent_set(g, d);
        if(ret.count() < vs.count()) ret = vs;
    }
    rep(i, n) if(g[v][i]) {
        d[i] = 1;
        rep(j, n) g[j][i] = 0;
    }
    BS vs = maximal_independent_set(g, d);
    vs[v] = 1;
    if(ret.count() < vs.count()) ret = vs;
    return ret;
}
#line 3 "src/test/yosupo_maximum_independent_set.cpp"

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,M;
    cin>>N>>M;
    vector<BS> G(N);
    rep(i,M){
        int u,v;
        cin>>u>>v;
        G[u][v]=G[v][u]=1;
    }
    BS ret=maximal_independent_set(G);
    cout<<ret.count()<<"\n";
    rep(i,N) if(ret[i]) cout<<i<<" ";
    cout<<"\n";
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	hack0_00	AC	4 ms	4 MB
g++	handmade_00	AC	4 ms	4 MB
g++	many_maximals_00	AC	8 ms	4 MB
g++	max_random_00	AC	4 ms	4 MB
g++	max_random_01	AC	5 ms	4 MB
g++	max_random_02	AC	10 ms	4 MB
g++	max_random_03	AC	6 ms	4 MB
g++	max_random_04	AC	4 ms	4 MB
g++	one_two_00	AC	632 ms	4 MB
g++	random_00	AC	5 ms	4 MB
g++	random_01	AC	4 ms	4 MB
g++	random_02	AC	4 ms	4 MB
g++	random_03	AC	4 ms	4 MB
g++	random_04	AC	4 ms	4 MB
clang++	example_00	AC	5 ms	4 MB
clang++	example_01	AC	4 ms	4 MB
clang++	hack0_00	AC	4 ms	4 MB
clang++	handmade_00	AC	4 ms	4 MB
clang++	many_maximals_00	AC	7 ms	4 MB
clang++	max_random_00	AC	5 ms	4 MB
clang++	max_random_01	AC	6 ms	4 MB
clang++	max_random_02	AC	9 ms	4 MB
clang++	max_random_03	AC	6 ms	4 MB
clang++	max_random_04	AC	5 ms	4 MB
clang++	one_two_00	AC	457 ms	4 MB
clang++	random_00	AC	5 ms	4 MB
clang++	random_01	AC	4 ms	4 MB
clang++	random_02	AC	4 ms	4 MB
clang++	random_03	AC	4 ms	4 MB
clang++	random_04	AC	4 ms	4 MB

Back to top page