枚举trick，CF 489D - Unbearable Controversy of Being

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

489D - Unbearable Controversy of Being

二、解题报告

1、思路分析

对于这种计算图形数目，最朴素的暴力无非是枚举每个顶点，这样时间复杂度会很高

策略往往是固定些点，然后枚举剩余的点

对于题目中要求的a,b,c,d构成的菱，我们可以固定a, c，然后统计多少b，满足a到b有边，b到c有边，那么a，c的贡献就是从b的集合中选两个数出来

那么代码如何实现？复杂度如何？

我们考虑枚举a，然后遍历a的邻接点b，再枚举b的邻接点c

此时a，c含义和上面一样，考虑将b的贡献加到c上面，即用数组cnt[]记录

这样遍历完后，cnt[c]就代表固定a,c 时b的数目，我们按照先前讨论的求贡献即可即C(cnt[c], 2)

时间复杂度分析：

外层枚举点是O(N)，枚举邻接点c，和c的邻接点b最坏情况下将整张网络的边遍历一遍，所以是O(M)，算贡献又是O(N)

所以总计为O(N(N + M))，上界还是比较宽松的

2、复杂度

时间复杂度： O(N(N + M))空间复杂度：O(N + M)

3、代码详解

 ​

#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
using PII = std::pair<int, int>;
using PIII = std::pair<int, PII>;
const int inf = 1e9 + 7, P = 1e9 + 7;

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> g(n);
    for (int i = 0, a, b; i < m; ++ i)
        std::cin >> a >> b,
        -- a, -- b,
        g[a].push_back(b);

    std::vector<int> cnt(n);
    int res = 0;
    for (int i = 0; i < n; ++ i) {
        for (int j : g[i])
            for (int k : g[j])
                ++ cnt[k];
        for (int j = 0; j < n; ++ j) {
            if (i != j)
                res += (cnt[j] - 1) * cnt[j] / 2;
            cnt[j] = 0;
        }
    }
    std::cout << res;
}


int main(int argc, char** argv) {
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_ --)
        solve();
    return 0;
}