test/library_checker/graph/maximum_independent_set.test.cpp

• View this file on GitHub
• Last update: 2024-10-31 23:51:11+09:00
• Problem: https://judge.yosupo.jp/problem/maximum_independent_set

Depends on

• Maximum Independent Set (最大独立集合) (lib/graph/maximum_independent_set.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/maximum_independent_set"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/graph/maximum_independent_set.hpp"

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

    int n, m; cin >> n >> m;
    vector<vector<int>> G(n);
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    vector<int> ans = maximumIndependentSet(G);
    cout << ans.size() << '\n';
    for(auto &v : ans){
        cout << v << " ";
    }
}

#line 1 "test/library_checker/graph/maximum_independent_set.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/maximum_independent_set"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/graph/maximum_independent_set.hpp"

/**
 * @brief Maximum Independent Set (最大独立集合)
 */

vector<int> maximumIndependentSet(vector<vector<int>> &G, int loop = 100000){
    const int MAX_V = 64;
    int n = G.size();
    assert(n <= MAX_V);
    vector<bitset<MAX_V>> g(n);
    for(int i = 0; i < n; i++){
        for(auto &v : G[i]){
            g[i][v] = 1;
        }
    }

    auto random_shuffle = [](vector<int> &p){
        int n = p.size();
        for(int i = n; i > 1; i--){
            int a = i - 1;
            int b = rand() % i;
            swap(p[a], p[b]);
        }
    };

    vector<int> ans;
    bitset<MAX_V> used, emp;
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    for(int k = 0; k < loop; k++){
        random_shuffle(p);
        vector<int> res;
        for(int i = 0; i < n; i++){
            if(used[p[i]]) continue;
            res.push_back(p[i]);
            used |= g[p[i]];
        }
        if(ans.size() < res.size()){
            swap(ans, res);
        }
        used &= emp;
    }
    return ans;
}
#line 6 "test/library_checker/graph/maximum_independent_set.test.cpp"

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

    int n, m; cin >> n >> m;
    vector<vector<int>> G(n);
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    vector<int> ans = maximumIndependentSet(G);
    cout << ans.size() << '\n';
    for(auto &v : ans){
        cout << v << " ";
    }
}

Back to top page