test/src/graph/enumerate_cliques/enumerate_cliques.test.cpp

• View this file on GitHub
• Last update: 2022-08-21 18:24:56+09:00
• Problem: https://judge.yosupo.jp/problem/enumerate_cliques

Depends on

• Enumerate Cliques (library/graph/enumerate_cliques.hpp)

Code

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

#include <iostream>
#include <atcoder/modint>

using mint = atcoder::modint998244353;

#include "library/graph/enumerate_cliques.hpp"

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

    int n, m;
    std::cin >> n >> m;

    std::vector<int> x(n);
    for (int &e : x) std::cin >> e;

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

    mint ans = 0;
    suisen::enumerate_cliques(
        g,
        [&ans, &x](const std::vector<int> &clique) {
            mint prod = 1;
            for (int i : clique) prod *= mint::raw(x[i]);
            ans += prod;
        }
    );
    std::cout << ans.val() << '\n';

    return 0;
}

#line 1 "test/src/graph/enumerate_cliques/enumerate_cliques.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_cliques"

#include <iostream>
#include <atcoder/modint>

using mint = atcoder::modint998244353;

#line 1 "library/graph/enumerate_cliques.hpp"



#include <algorithm>
#include <vector>

namespace suisen {
    /**
     * Type Parameters
     * - CliqueComsumer : type of consumer function std::vector<int> -> void
     * 
     * Parameters
     * - std::vector<std::vector<int>> g : simple undirected graph
     * - CliqueComsumer fun
     * 
     * Requirements
     * - v in g[u] <=> u in g[v]
     * 
     * Complexity
     * - time : O(2^sqrt(2M) * N + (sum of size of cliques)) = O(2^sqrt(2M) * N * sqrt(2M)) ?
     * - space : O(N + M)
     */
    template <typename CliqueComsumer>
    void enumerate_cliques(std::vector<std::vector<int>> g, CliqueComsumer &&fun) {
        const int n = g.size();
        // sort by degree
        std::vector<int> ord(n), idx(n);
        std::iota(ord.begin(), ord.end(), 0);
        std::sort(ord.begin(), ord.end(), [&](int i, int j) { return g[i].size() < g[j].size(); });
        for (int i = 0; i < n; ++i) idx[ord[i]] = i;
        for (int i = 0; i < n; ++i) {
            g[i].erase(std::remove_if(g[i].begin(), g[i].end(), [&](int j) { return idx[j] < idx[i]; }), g[i].end());
            std::sort(g[i].begin(), g[i].end(), [&](int x, int y) { return idx[x] < idx[y]; });
        }

        std::vector<int> id(n, -1), inv_id(n);
        std::vector<int> clique(n);
        for (int i : ord) {
            const int l = g[i].size();
            for (int p = 0; p < l; ++p) {
                int j = g[i][p];
                inv_id[id[j] = p] = j;
            }
            std::vector<int> st(l);
            for (int p = 0; p < l; ++p) {
                st[p] = (1 << (p + 1)) - 1;
                for (int j : g[g[i][p]]) if (int k = id[j]; k >= 0) st[p] |= 1 << k;
            }
            std::vector<int>::iterator it = clique.begin();
            *it++ = i;
            fun(std::vector<int>(clique.begin(), it));
            std::vector<int> intersec(l, (1 << l) - 1);
            for (int c = 1; c < 1 << l; ++c) {
                const int k = __builtin_ctz(c);
                std::fill(intersec.begin(), intersec.begin() + k, intersec[k] &= st[k]);
                *(it -= k)++ = inv_id[k];
                if ((intersec[0] & c) == c) fun(std::vector<int>(clique.begin(), it));
            }
            for (int j : g[i]) id[j] = -1;
        }
    }
} // namespace suisen


#line 9 "test/src/graph/enumerate_cliques/enumerate_cliques.test.cpp"

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

    int n, m;
    std::cin >> n >> m;

    std::vector<int> x(n);
    for (int &e : x) std::cin >> e;

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

    mint ans = 0;
    suisen::enumerate_cliques(
        g,
        [&ans, &x](const std::vector<int> &clique) {
            mint prod = 1;
            for (int i : clique) prod *= mint::raw(x[i]);
            ans += prod;
        }
    );
    std::cout << ans.val() << '\n';

    return 0;
}

Back to top page