cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub rniya/cp-library

:warning: Count Cliques
(src/graph/count_clique.hpp)

概要

$n$ 頂点の自己ループを含まないグラフ $G$ のクリークの個数を数える．

問題例

Depends on

Code

#pragma once
#include <algorithm>
#include "count_independent_set.hpp"

template <typename T> T count_clique(const std::vector<std::vector<int>>& G) {
    int n = G.size();
    T res = 1;
    std::vector<int> deg(n), idx(n, -1);
    for (int i = 0; i < n; i++) deg[i] = G[i].size();
    while (true) {
        int v = -1;
        for (int i = 0; i < n; i++) {
            if (deg[i] != -1 and (v == -1 or deg[i] < deg[v])) {
                v = i;
            }
        }
        if (v == -1) break;
        deg[v] = -1;
        int adj = 0;
        for (const int& u : G[v]) {
            if (deg[u] == -1) continue;
            --deg[u];
            idx[u] = adj++;
        }
        std::vector<unsigned long long> g(adj, (1ULL << adj) - 1);
        for (const int& u : G[v]) {
            if (idx[u] == -1) continue;
            int x = idx[u];
            g[x] &= ~(1ULL << x);
            for (const int& w : G[u]) {
                if (idx[w] == -1) continue;
                int y = idx[w];
                g[x] &= ~(1ULL << y);
                g[y] &= ~(1ULL << x);
            }
        }
        res += count_independent_set(g);
        for (const int& u : G[v]) {
            if (deg[u] == -1) continue;
            idx[u] = -1;
        }
    }
    return res;
}
#line 2 "src/graph/count_clique.hpp"
#include <algorithm>
#line 2 "src/graph/count_independent_set.hpp"
#include <cassert>
#include <vector>

namespace internal {

unsigned long long f(unsigned long long,
                     const std::vector<unsigned long long>&,
                     const std::vector<unsigned long long>&,
                     const std::vector<unsigned long long>&);
unsigned long long g(unsigned long long,
                     const std::vector<unsigned long long>&,
                     const std::vector<unsigned long long>&,
                     const std::vector<unsigned long long>&);

unsigned long long f(unsigned long long S,
                     const std::vector<unsigned long long>& G,
                     const std::vector<unsigned long long>& path,
                     const std::vector<unsigned long long>& cycle) {
    unsigned long long res = 1;
    for (; S;) {
        int v = __builtin_ctzll(S);
        unsigned long long comp = 1ULL << v, seen = 0;
        for (; comp & ~seen;) {
            int u = __builtin_ctzll(comp & ~seen);
            comp |= G[u] & S;
            seen |= 1ULL << u;
        }
        res *= g(comp, G, path, cycle);
        S &= ~comp;
    }
    return res;
}

unsigned long long g(unsigned long long S,
                     const std::vector<unsigned long long>& G,
                     const std::vector<unsigned long long>& path,
                     const std::vector<unsigned long long>& cycle) {
    if (!S) return 1;
    if (!(S & (S - 1))) return 2;
    int maxi = -1, argmax = -1, one = 0, tot = __builtin_popcountll(S);
    for (unsigned long long T = S; T;) {
        int v = __builtin_ctzll(T);
        T &= ~(1ULL << v);
        int deg = __builtin_popcountll(G[v] & S);
        if (maxi < deg) {
            maxi = deg;
            argmax = v;
        }
        one += (deg == 1);
    }
    if (maxi <= 2) return one ? path[tot] : cycle[tot];
    S &= ~(1ULL << argmax);
    return f(S, G, path, cycle) + f(S & ~G[argmax], G, path, cycle);
}

}  // namespace internal

unsigned long long count_independent_set(const std::vector<unsigned long long>& G) {
    int n = G.size();
    assert(n < 64);
    if (n == 0) return 1;
    std::vector<unsigned long long> path(n + 1), cycle(n + 1);
    path[0] = 1, path[1] = 2;
    for (int i = 2; i <= n; i++) path[i] = path[i - 1] + path[i - 2];
    cycle[0] = 2, cycle[1] = 1;
    for (int i = 2; i <= n; i++) cycle[i] = cycle[i - 1] + cycle[i - 2];
    return internal::f((1ULL << n) - 1, G, path, cycle);
}
#line 4 "src/graph/count_clique.hpp"

template <typename T> T count_clique(const std::vector<std::vector<int>>& G) {
    int n = G.size();
    T res = 1;
    std::vector<int> deg(n), idx(n, -1);
    for (int i = 0; i < n; i++) deg[i] = G[i].size();
    while (true) {
        int v = -1;
        for (int i = 0; i < n; i++) {
            if (deg[i] != -1 and (v == -1 or deg[i] < deg[v])) {
                v = i;
            }
        }
        if (v == -1) break;
        deg[v] = -1;
        int adj = 0;
        for (const int& u : G[v]) {
            if (deg[u] == -1) continue;
            --deg[u];
            idx[u] = adj++;
        }
        std::vector<unsigned long long> g(adj, (1ULL << adj) - 1);
        for (const int& u : G[v]) {
            if (idx[u] == -1) continue;
            int x = idx[u];
            g[x] &= ~(1ULL << x);
            for (const int& w : G[u]) {
                if (idx[w] == -1) continue;
                int y = idx[w];
                g[x] &= ~(1ULL << y);
                g[y] &= ~(1ULL << x);
            }
        }
        res += count_independent_set(g);
        for (const int& u : G[v]) {
            if (deg[u] == -1) continue;
            idx[u] = -1;
        }
    }
    return res;
}
Back to top page