無向グラフに含まれる三角形の列挙
(other_algorithms/enumerate_triangles.hpp)

• View this file on GitHub
• Last update: 2021-06-13 19:44:51+09:00
• Include: #include "other_algorithms/enumerate_triangles.hpp"
• Link: https://www.slideshare.net/catupper/trianguler

頂点数 $N$，辺数 $M$ の無向単純グラフで辺 $(s, t), (t, u), (u, s)$ が全て存在するような相異なる 3 頂点 $(s, t, u)$ の三つ組を全列挙する．時間計算量は $O(N + M \sqrt{M})$．なお完全グラフの場合に三角形は実際に $O(M \sqrt{M})$ 個できる．

使用方法

EnumerateTriangles graph(N);
for (auto [u, v] : edges) graph.add_edge(u, v);
auto f = [&](int i, int j, int k) { ret += solve_problem(i, j, k); }; // 三角形の各頂点番号を引数にとる
graph.run(f);

リンク

• Library Checker: Enumerate Triangles
• catupper さんの解説

Verified with

• other_algorithms/test/enumerate_triangles.test.cpp

Code

#pragma once
#include <cassert>
#include <utility>
#include <vector>

// CUT begin
// Enumerate triangles
// Complexity: O(N + M \sqrt{M})
// Reference:
// - https://www.slideshare.net/catupper/trianguler
struct EnumerateTriangles {
    int V;
    std::vector<int> deg;
    std::vector<std::vector<int>> to;
    std::vector<std::pair<int, int>> edges;
    EnumerateTriangles(int N = 0) : V(N), deg(N), to(N) {}
    void add_edge(int s, int t) {
        assert(s >= 0 and s < V);
        assert(t >= 0 and t < V);
        assert(s != t);
        edges.emplace_back(s, t);
        deg[s]++, deg[t]++;
    }
    template <class F> void run(F f) {
        auto comp = [&](int i, int j) { return deg[i] != deg[j] ? deg[i] < deg[j] : i < j; };
        for (auto p : edges) {
            int s = p.first, t = p.second;
            if (comp(s, t)) {
                to[s].push_back(t);
            } else {
                to[t].push_back(s);
            }
        }
        std::vector<char> flag(V);
        for (int i = 0; i < V; i++) {
            for (auto j : to[i]) flag[j] = 1;
            for (auto j : to[i]) {
                for (auto k : to[j]) {
                    if (flag[k]) f(i, j, k);
                }
            }
            for (auto j : to[i]) flag[j] = 0;
        }
    }
};

#line 2 "other_algorithms/enumerate_triangles.hpp"
#include <cassert>
#include <utility>
#include <vector>

// CUT begin
// Enumerate triangles
// Complexity: O(N + M \sqrt{M})
// Reference:
// - https://www.slideshare.net/catupper/trianguler
struct EnumerateTriangles {
    int V;
    std::vector<int> deg;
    std::vector<std::vector<int>> to;
    std::vector<std::pair<int, int>> edges;
    EnumerateTriangles(int N = 0) : V(N), deg(N), to(N) {}
    void add_edge(int s, int t) {
        assert(s >= 0 and s < V);
        assert(t >= 0 and t < V);
        assert(s != t);
        edges.emplace_back(s, t);
        deg[s]++, deg[t]++;
    }
    template <class F> void run(F f) {
        auto comp = [&](int i, int j) { return deg[i] != deg[j] ? deg[i] < deg[j] : i < j; };
        for (auto p : edges) {
            int s = p.first, t = p.second;
            if (comp(s, t)) {
                to[s].push_back(t);
            } else {
                to[t].push_back(s);
            }
        }
        std::vector<char> flag(V);
        for (int i = 0; i < V; i++) {
            for (auto j : to[i]) flag[j] = 1;
            for (auto j : to[i]) {
                for (auto k : to[j]) {
                    if (flag[k]) f(i, j, k);
                }
            }
            for (auto j : to[i]) flag[j] = 0;
        }
    }
};

Back to top page