other_algorithms/test/enumerate_triangles.test.cpp

• View this file on GitHub
• Last update: 2022-01-08 20:23:44+09:00
• Problem: https://judge.yosupo.jp/problem/enumerate_triangles

Depends on

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

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_triangles"
#include "../enumerate_triangles.hpp"
#include <iostream>
#include <vector>
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    EnumerateTriangles graph(N);
    vector<unsigned> X(N);
    for (auto &x : X) cin >> x;
    while (M--) {
        int u, v;
        cin >> u >> v;
        graph.add_edge(u, v);
    }
    unsigned long long ret = 0;
    constexpr unsigned md = 998244353;
    auto f = [&](int i, int j, int k) {
        (ret += (unsigned long long)X[i] * X[j] % md * X[k]) %= md;
    };
    graph.run(f);
    cout << ret << '\n';
}

#line 1 "other_algorithms/test/enumerate_triangles.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_triangles"
#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;
        }
    }
};
#line 3 "other_algorithms/test/enumerate_triangles.test.cpp"
#include <iostream>
#line 5 "other_algorithms/test/enumerate_triangles.test.cpp"
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    EnumerateTriangles graph(N);
    vector<unsigned> X(N);
    for (auto &x : X) cin >> x;
    while (M--) {
        int u, v;
        cin >> u >> v;
        graph.add_edge(u, v);
    }
    unsigned long long ret = 0;
    constexpr unsigned md = 998244353;
    auto f = [&](int i, int j, int k) {
        (ret += (unsigned long long)X[i] * X[j] % md * X[k]) %= md;
    };
    graph.run(f);
    cout << ret << '\n';
}

Back to top page