test/src/graph/enumerate_triangles/abc258_g.test.cpp

• View this file on GitHub
• Last update: 2022-07-10 15:07:59+09:00
• Problem: https://atcoder.jp/contests/abc258/tasks/abc258_g

Depends on

• 三角形列挙 (library/graph/enumerate_triangles.hpp)

Code

#define PROBLEM "https://atcoder.jp/contests/abc258/tasks/abc258_g"

#include <iostream>

#include "library/graph/enumerate_triangles.hpp"

int main() {
    int n;
    std::cin >> n;
    
    std::vector<std::vector<int>> g(n);
    for (int u = 0; u < n; ++u) {
        std::string s;
        std::cin >> s;
        for (int v = 0; v < n; ++v) if (s[v] == '1') {
            g[u].push_back(v);
        }
    }

    long long ans = 0;
    suisen::enumerate_triangles(g, [&ans](int, int, int) { ++ans; });
    std::cout << ans << std::endl;

    return 0;
}

#line 1 "test/src/graph/enumerate_triangles/abc258_g.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc258/tasks/abc258_g"

#include <iostream>

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



#include <algorithm>
#include <vector>

namespace suisen {
    /**
     * Type Parameters
     * - TriangleConsumer : type of consumer function (int, int, int) -> void
     * 
     * Parameters
     * - std::vector<std::vector<int>> g : simple undirected graph
     * - TriangleConsumer fun
     * 
     * Requirements
     * - v in g[u] <=> u in g[v]
     * 
     * Complexity
     * - time : O(N + M^{3/2})
     * - space : O(N + M)
     */
    template <typename TriangleConsumer>
    void enumerate_triangles(std::vector<std::vector<int>> g, TriangleConsumer &&fun) {
        const int n = g.size();
        std::vector<int> cnt(n + 1);
        for (int i = 0; i < n; ++i) ++cnt[g[i].size() + 1];
        for (int i = 0; i < n; ++i) cnt[i + 1] += cnt[i];
        std::vector<int> ord(n), idx(n);
        for (int i = 0; i < n; ++i) ord[idx[i] = cnt[g[i].size()]++] = 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::vector<int8_t> exists(n, false);
        for (int i : ord) {
            for (int j : g[i]) exists[j] = true;
            for (int j : g[i]) for (int k : g[j]) if (exists[k]) fun(i, j, k);
            for (int j : g[i]) exists[j] = false;
        }
    }
} // namespace suisen


#line 6 "test/src/graph/enumerate_triangles/abc258_g.test.cpp"

int main() {
    int n;
    std::cin >> n;
    
    std::vector<std::vector<int>> g(n);
    for (int u = 0; u < n; ++u) {
        std::string s;
        std::cin >> s;
        for (int v = 0; v < n; ++v) if (s[v] == '1') {
            g[u].push_back(v);
        }
    }

    long long ans = 0;
    suisen::enumerate_triangles(g, [&ans](int, int, int) { ++ans; });
    std::cout << ans << std::endl;

    return 0;
}

Back to top page