cp-library

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

View the Project on GitHub rniya/cp-library

:heavy_check_mark: Enuemrate $C_3$, Count $C_4, K_4$
(src/graph/count_graphs.hpp)

概要

$n$ 頂点 $m$ 辺の無向グラフ $G$ に含まれる $C_3$ の列挙及び $C_4, K_4$ の数え上げを以下に述べる時間計算量で行う．

基本的には各辺を次数の小さい頂点から大きい頂点に向き付けた有向グラフ $H$ を考えることにする． このとき，各頂点の次数は $\sqrt{2 m}$ で抑えることができる．

$C_3$

$H$ 上で $a$ から辺が出ている点 $b$，$b$ から辺が出ている点 $c$ を走査する． $1$ 本目の辺が $m$ 本で，$2$ 本目の辺がそれぞれ $\mathrm{O}(\sqrt{m})$ 本だから全体で $\mathrm{O}(m\sqrt{m})$ 時間で計算可能である．

$C_4$

$4$ 頂点のうち次数が最大の点 $c$ の対角にある頂点 $a$ を固定する． $1, 2$ 本目の辺をそれぞれ $G, H$ 上にとるような $a$ から $c$ への長さ $2$ のパスを $2$ つ選ぶ選び方を合計すれば良い．

計算量は $\mathrm{O}(m \sqrt{m})$．

$K_4$

$K_4$ に含まれる頂点のうち最も小さい頂点 $a$ を固定する． $a, b, c, d$ が $K_4$ を成すのは $H$ 上で $a$ から $b, c, d$ に辺が張られており，かつ $b, c, d$ が $G$ 上で $C_3$ を成すのと同値であるから，$a$ の $H$ での隣接点からなる誘導部分グラフの中で $C_3$ を数えればよい．

計算量はワードサイズを $w$ として $\mathrm{O}\left(m \sqrt{m} + \frac{m^2}{w}\right)$．

問題例

Verified with

Code

#pragma once
#include <algorithm>
#include <tuple>
#include <vector>

namespace count_graphs {

std::vector<std::tuple<int, int, int>> enumerate_C3(const std::vector<std::vector<int>>& G) {
    int n = G.size();
    std::vector<int> deg(n);
    for (int i = 0; i < n; i++) deg[i] = G[i].size();
    auto comp = [&](int u, int v) -> bool { return deg[u] != deg[v] ? deg[u] < deg[v] : u < v; };
    std::vector<std::vector<int>> H(n);
    for (int i = 0; i < n; i++) {
        for (const int& j : G[i]) {
            if (comp(i, j)) {
                H[i].emplace_back(j);
            }
        }
    }
    std::vector<bool> f(n, false);
    std::vector<std::tuple<int, int, int>> res;
    for (int i = 0; i < n; i++) {
        for (int& j : H[i]) f[j] = true;
        for (int& j : H[i]) {
            for (int& k : H[j]) {
                if (f[k]) {
                    res.emplace_back(i, j, k);
                }
            }
        }
        for (int& j : H[i]) f[j] = false;
    }
    return res;
}

long long count_C4(const std::vector<std::vector<int>>& G) {
    int n = G.size();
    std::vector<int> deg(n);
    for (int i = 0; i < n; i++) deg[i] = G[i].size();
    auto comp = [&](int u, int v) -> bool { return deg[u] != deg[v] ? deg[u] < deg[v] : u < v; };
    std::vector<std::vector<int>> H(n);
    for (int i = 0; i < n; i++) {
        for (const int& j : G[i]) {
            if (comp(i, j)) {
                H[i].emplace_back(j);
            }
        }
    }
    std::vector<int> f(n, 0);
    long long res = 0;
    for (int i = 0; i < n; i++) {
        for (const int& j : G[i]) {
            for (const int& k : H[j]) {
                if (comp(i, k)) {
                    res += f[k];
                    f[k]++;
                }
            }
        }
        for (const int& j : G[i]) {
            for (const int& k : H[j]) {
                f[k] = 0;
            }
        }
    }
    return res;
}

long long count_K4(const std::vector<std::vector<int>>& G) {
    int n = G.size();
    std::vector<int> deg(n);
    for (int i = 0; i < n; i++) deg[i] = G[i].size();
    auto comp = [&](int u, int v) -> bool { return deg[u] != deg[v] ? deg[u] < deg[v] : u < v; };
    std::vector<std::vector<int>> H(n);
    for (int i = 0; i < n; i++) {
        for (const int& j : G[i]) {
            if (comp(i, j)) {
                H[i].emplace_back(j);
            }
        }
    }
    long long res = 0;
    std::vector<int> idx(n, -1);
    constexpr int B = 64;
    for (int i = 0; i < n; i++) {
        int len = H[i].size();
        for (int j = 0; j < len; j++) idx[H[i][j]] = j;
        std::vector<std::vector<int>> I(len);
        for (int j = 0; j < len; j++) {
            for (int& u : H[H[i][j]]) {
                if (idx[u] == -1) continue;
                I[j].emplace_back(idx[u]);
            }
        }
        for (int b = 0; b < (len + B - 1) / B; b++) {
            int L = B * b, R = std::min(len, L + B);
            std::vector<unsigned long long> adj(len, 0);
            for (int j = L; j < R; j++) {
                for (const int& k : I[j]) {
                    adj[k] |= 1ULL << (j - L);
                }
            }
            for (int j = 0; j < len; j++) {
                for (const int& k : I[j]) {
                    res += __builtin_popcountll(adj[j] & adj[k]);
                }
            }
        }
        for (int j = 0; j < len; j++) idx[H[i][j]] = -1;
    }
    return res;
}

}  // namespace count_graphs
#line 2 "src/graph/count_graphs.hpp"
#include <algorithm>
#include <tuple>
#include <vector>

namespace count_graphs {

std::vector<std::tuple<int, int, int>> enumerate_C3(const std::vector<std::vector<int>>& G) {
    int n = G.size();
    std::vector<int> deg(n);
    for (int i = 0; i < n; i++) deg[i] = G[i].size();
    auto comp = [&](int u, int v) -> bool { return deg[u] != deg[v] ? deg[u] < deg[v] : u < v; };
    std::vector<std::vector<int>> H(n);
    for (int i = 0; i < n; i++) {
        for (const int& j : G[i]) {
            if (comp(i, j)) {
                H[i].emplace_back(j);
            }
        }
    }
    std::vector<bool> f(n, false);
    std::vector<std::tuple<int, int, int>> res;
    for (int i = 0; i < n; i++) {
        for (int& j : H[i]) f[j] = true;
        for (int& j : H[i]) {
            for (int& k : H[j]) {
                if (f[k]) {
                    res.emplace_back(i, j, k);
                }
            }
        }
        for (int& j : H[i]) f[j] = false;
    }
    return res;
}

long long count_C4(const std::vector<std::vector<int>>& G) {
    int n = G.size();
    std::vector<int> deg(n);
    for (int i = 0; i < n; i++) deg[i] = G[i].size();
    auto comp = [&](int u, int v) -> bool { return deg[u] != deg[v] ? deg[u] < deg[v] : u < v; };
    std::vector<std::vector<int>> H(n);
    for (int i = 0; i < n; i++) {
        for (const int& j : G[i]) {
            if (comp(i, j)) {
                H[i].emplace_back(j);
            }
        }
    }
    std::vector<int> f(n, 0);
    long long res = 0;
    for (int i = 0; i < n; i++) {
        for (const int& j : G[i]) {
            for (const int& k : H[j]) {
                if (comp(i, k)) {
                    res += f[k];
                    f[k]++;
                }
            }
        }
        for (const int& j : G[i]) {
            for (const int& k : H[j]) {
                f[k] = 0;
            }
        }
    }
    return res;
}

long long count_K4(const std::vector<std::vector<int>>& G) {
    int n = G.size();
    std::vector<int> deg(n);
    for (int i = 0; i < n; i++) deg[i] = G[i].size();
    auto comp = [&](int u, int v) -> bool { return deg[u] != deg[v] ? deg[u] < deg[v] : u < v; };
    std::vector<std::vector<int>> H(n);
    for (int i = 0; i < n; i++) {
        for (const int& j : G[i]) {
            if (comp(i, j)) {
                H[i].emplace_back(j);
            }
        }
    }
    long long res = 0;
    std::vector<int> idx(n, -1);
    constexpr int B = 64;
    for (int i = 0; i < n; i++) {
        int len = H[i].size();
        for (int j = 0; j < len; j++) idx[H[i][j]] = j;
        std::vector<std::vector<int>> I(len);
        for (int j = 0; j < len; j++) {
            for (int& u : H[H[i][j]]) {
                if (idx[u] == -1) continue;
                I[j].emplace_back(idx[u]);
            }
        }
        for (int b = 0; b < (len + B - 1) / B; b++) {
            int L = B * b, R = std::min(len, L + B);
            std::vector<unsigned long long> adj(len, 0);
            for (int j = L; j < R; j++) {
                for (const int& k : I[j]) {
                    adj[k] |= 1ULL << (j - L);
                }
            }
            for (int j = 0; j < len; j++) {
                for (const int& k : I[j]) {
                    res += __builtin_popcountll(adj[j] & adj[k]);
                }
            }
        }
        for (int j = 0; j < len; j++) idx[H[i][j]] = -1;
    }
    return res;
}

}  // namespace count_graphs
Back to top page