library

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

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Enumerate Triangle
(Graph/enumtriangle.hpp)

• View this file on GitHub
• Last update: 2024-12-12 04:29:08+09:00
• Include: #include "Graph/enumtriangle.hpp"

Code

#pragma once

// query(u,v,w,i,j,k): vertex {u,v,w}, edge {i,j,k}
template <typename F>
void EnumTriangle(int n, vector<pair<int, int>> &es, F query) {
    using P = pair<int, int>;
    vector<int> deg(n);
    for (auto &[x, y] : es)
        deg[x]++, deg[y]++;
    vector H(n, vector<P>());
    rep(i, 0, SZ(es)) {
        auto [x, y] = es[i];
        if (P{deg[x], x} < P{deg[y], y})
            H[x].push_back({y, i});
        else
            H[y].push_back({x, i});
    }
    vector<int> used(n, -1);
    rep(u, 0, n) {
        for (auto &[v, i] : H[u])
            used[v] = i;
        for (auto &[v, j] : H[u]) {
            for (auto &[w, k] : H[v])
                if (used[w] != -1) {
                    query(u, v, w, used[w], j, k);
                }
        }
        for (auto &[v, i] : H[u])
            used[v] = -1;
    }
}

/**
 * @brief Enumerate Triangle
 */

#line 2 "Graph/enumtriangle.hpp"

// query(u,v,w,i,j,k): vertex {u,v,w}, edge {i,j,k}
template <typename F>
void EnumTriangle(int n, vector<pair<int, int>> &es, F query) {
    using P = pair<int, int>;
    vector<int> deg(n);
    for (auto &[x, y] : es)
        deg[x]++, deg[y]++;
    vector H(n, vector<P>());
    rep(i, 0, SZ(es)) {
        auto [x, y] = es[i];
        if (P{deg[x], x} < P{deg[y], y})
            H[x].push_back({y, i});
        else
            H[y].push_back({x, i});
    }
    vector<int> used(n, -1);
    rep(u, 0, n) {
        for (auto &[v, i] : H[u])
            used[v] = i;
        for (auto &[v, j] : H[u]) {
            for (auto &[w, k] : H[v])
                if (used[w] != -1) {
                    query(u, v, w, used[w], j, k);
                }
        }
        for (auto &[v, i] : H[u])
            used[v] = -1;
    }
}

/**
 * @brief Enumerate Triangle
 */

Back to top page