Graph/tests/clique_maxindependentset.test.cpp

View this file on GitHub
Last update: 2022-01-06 04:21:41+08:00
Problem: https://judge.yosupo.jp/problem/maximum_independent_set

Depends on

Graph/MaxClique.h

Code

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

#include <bits/stdc++.h>
using namespace std;

#include "../MaxClique.h"

bool edge[44][44];

#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;

    REP(i,m) {
        int u, v; cin >> u >> v;
        edge[u][v] = edge[v][u] = 1;
    }

    MaxClique g(n);
    REP(i,n) REP(j,n) if (!edge[i][j] && i != j) {
        g.addEdge(i, j);
    }

    auto res = g.solve();
    cout << res.size() << endl;
    for (int x : res) {
        cout << x << ' ';
    }
    cout << endl;
    return 0;
}

#line 1 "Graph/tests/clique_maxindependentset.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/maximum_independent_set"

#include <bits/stdc++.h>
using namespace std;

#line 1 "Graph/MaxClique.h"
// MaxClique
// Copied from https://judge.yosupo.jp/submission/15825
//
// 0-based index
//
// Tested:
// - https://judge.yosupo.jp/problem/maximum_independent_set
struct MaxClique {
    static const int MN = 64; // change to bitset for n > 64
    int n, deg[MN];
    uint64_t g[MN], ans;
    vector<pair<int,int>> edges;

    MaxClique(int _n) : n(_n) {
        fill(g, g+n, 0ull);
        fill(deg, deg+n, 0);
        edges.clear();
    }

    // Add bi-directional edge
    // 0-based index
    void addEdge(int u, int v) {
        edges.emplace_back(u, v);
        ++deg[u]; ++deg[v];
    }

    vector<int> solve() {
        vector<int> ord(n);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&] (int u, int v) { return deg[u] < deg[v]; });
        vector<int> id(n);
        for (int i = 0; i < n; i++) id[ord[i]] = i;

        for (const auto& e : edges) {
            int u = id[e.first], v = id[e.second];
            g[u] |= 1ull << v;
            g[v] |= 1ull << u;
        }
        uint64_t r = 0, p = (1ull << n) - 1;
        ans = 0;
        dfs(r, p);
        vector<int> res;
        for (int i = 0; i < n; i++) {
            if ((ans >> i) & 1) res.push_back(ord[i]);
        }
        return res;
    }

#define cnt __builtin_popcountll
    void dfs(uint64_t r, uint64_t p) {
        if (p == 0) {
            if (cnt(r) > cnt(ans)) ans = r;
            return;
        }
        if (cnt(r | p) <= cnt(ans)) return;
        int x = __builtin_ctzll(p & -p);
        uint64_t c = p;
        while (c > 0) {
            x = __builtin_ctzll(c & -c);
            r |= 1ull << x;
            dfs(r, p & g[x]);
            r &= ~(1ull << x);
            p &= ~(1ull << x);
            c ^= 1ull << x;
        }
    }
};
#line 7 "Graph/tests/clique_maxindependentset.test.cpp"

bool edge[44][44];

#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;

    REP(i,m) {
        int u, v; cin >> u >> v;
        edge[u][v] = edge[v][u] = 1;
    }

    MaxClique g(n);
    REP(i,n) REP(j,n) if (!edge[i][j] && i != j) {
        g.addEdge(i, j);
    }

    auto res = g.solve();
    cout << res.size() << endl;
    for (int x : res) {
        cout << x << ' ';
    }
    cout << endl;
    return 0;
}