解题思路

• 定义回顾：四个不同点 a,b,c,d 构成“菱形”当且仅当存在有向边 a→b, b→c, a→d, d→c。
• 等价转化：固定一对有序端点 (a,c)，设能把 a 接到 c 的不同中间点（即 a→x 且 x→c 的点）个数为 k，则可由它们两两配对形成 C(k,2) 个菱形。
• 实现：对每个源点 a，遍历所有两步路径 a→b→c，用数组 cnt[c] 统计到该 c 的不同中间点数；只记录出现过的 c（列表 touched），最后对每个被访问的 c 把 C(cnt[c],2) 加入答案。遍历时排除 c==a 和 c==b，同时忽略自环 u==v，以确保四点互异。

复杂度分析

• 总时间复杂度： 对每条边 a→b 再枚举 b 的出边，共为 O(∑_v in[v]·out[v])；由于只遍历出现过的 c，没有额外的 O(n^2)。
• 空间复杂度：O(n + m)（邻接表 + 计数数组）。

代码实现

Python

# -*- coding: utf-8 -*-
import sys

def count_diamonds(n, edges):
    """统计菱形数量：对每对(a,c)按中间点两两配对"""
    # 建立出边邻接表
    out = [[] for _ in range(n + 1)]
    for u, v in edges:
        if u != v:           # 忽略自环
            out[u].append(v)

    ans = 0
    # 枚举源点 a
    for a in range(1, n + 1):
        cnt = [0] * (n + 1)  # cnt[c]: a 到 c 的不同中间点数量
        touched = []         # 只记录被访问到的 c，避免 O(n) 扫描
        for b in out[a]:
            if b == a:
                continue
            for c in out[b]:
                # 确保四点互异：c 不能等于 a 或 b
                if c != a and c != b:
                    if cnt[c] == 0:
                        touched.append(c)  # 第一次访问该 c
                    cnt[c] += 1
        # 只遍历出现过的 c，累加组合数 C(k,2)
        for c in touched:
            k = cnt[c]
            if k >= 2:
                ans += k * (k - 1) // 2
    return ans

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    n, m = data[0], data[1]
    edges = []
    idx = 2
    for _ in range(m):
        u, v = data[idx], data[idx + 1]
        edges.append((u, v))
        idx += 2
    print(count_diamonds(n, edges))

if __name__ == "__main__":
    main()

Java

// -*- coding: utf-8 -*-
import java.io.*;
import java.util.*;

/**
 * ACM 风格，类名统一为 Main
 * 思路：对每个 a 统计所有两步路径 a->b->c 的终点 c 的不同中间点数量，
 *      仅遍历出现过的 c，累加 C(k,2)。
 */
public class Main {

    // 功能函数：计算菱形数量
    static long countDiamonds(int n, List<int[]> edges) {
        // 建立出边邻接表
        ArrayList<Integer>[] out = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) out[i] = new ArrayList<>();
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            if (u != v) out[u].add(v); // 忽略自环
        }

        long ans = 0L;
        // 枚举源点 a
        for (int a = 1; a <= n; a++) {
            int[] cnt = new int[n + 1];            // cnt[c]
            ArrayList<Integer> touched = new ArrayList<>(); // 只记录出现过的 c
            for (int b : out[a]) {
                if (b == a) continue;
                for (int c : out[b]) {
                    if (c != a && c != b) {
                        if (cnt[c] == 0) touched.add(c); // 第一次访问 c
                        cnt[c]++;
                    }
                }
            }
            // 累加组合数 C(k,2)
            for (int c : touched) {
                long k = cnt[c];
                if (k >= 2) ans += k * (k - 1) / 2;
            }
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        // 输入：第一行 n m，接着 m 行 u v
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String first = br.readLine();
        if (first == null || first.trim().isEmpty()) return;
        StringTokenizer st = new StringTokenizer(first);
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            edges.add(new int[]{u, v});
        }
        System.out.println(countDiamonds(n, edges));
    }
}

C++

// -*- coding: utf-8 -*-
#include <bits/stdc++.h>
using namespace std;

/*
 功能函数：计算菱形数量
 方法：对每个 a 统计两步路径 a->b->c 的终点 c 的不同中间点数，
      只遍历出现过的 c，答案累加 C(cnt[c], 2)。
*/
long long count_diamonds(int n, const vector<pair<int,int>>& edges) {
    // 建立出边邻接表
    vector<vector<int>> out(n + 1);
    for (auto e : edges) {
        int u = e.first, v = e.second;
        if (u != v) out[u].push_back(v); // 忽略自环
    }

    long long ans = 0;
    for (int a = 1; a <= n; ++a) {
        vector<int> cnt(n + 1, 0); // cnt[c]
        vector<int> touched;       // 仅记录出现过的 c
        for (int b : out[a]) {
            if (b == a) continue;
            for (int c : out[b]) {
                if (c != a && c != b) {
                    if (cnt[c] == 0) touched.push_back(c); // 第一次访问 c
                    cnt[c]++; // a->b->c 的中间点数加一
                }
            }
        }
        // 累加组合数
        for (int c : touched) {
            long long k = cnt[c];
            if (k >= 2) ans += k * (k - 1) / 2;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<pair<int,int>> edges;
    edges.reserve(m);
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        edges.emplace_back(u, v);
    }
    cout << count_diamonds(n, edges) << "\n";
    return 0;
}

题目内容

小明来到一个新的城市，当他看到城市里四个不同的地点 $a、b、c$ 和 $d$ 时，如果存在两条从 $a$ 到 $c$ 的路径————一条通过 $b$ ，另一条通过 $d$，他就称这个四个地点组合为“菱形”。

菱形的定义:

$a、b、c、d$ 四个不同的地点，满足以下条件:

$(a,b)、(b,c)、(a,d)、(d,c)$ 这些道路是直接连接的。

也就是说，$a$ 到 $c$ 有两条不同的路径:一条通过 $b$ ，另一条通过 $d$ .(画出来有可能是凹四面形)

给定一个城市的地点和道路的信息，小明想计算出有多少个“菱形"。

备注:

道路信息是单向的，如 $1$ $2$ 表示从 $1$ 到 $2$ 的单向路径，$2$ $1$ 表示从 $2$ 到 $1$ 的单向路径

输入描述

第一行包含两个整数 $n$ 和 $m$ ($n$ 和 $m$ 使用空格隔开)，其中 $n$ 表示地点的数量，$m$ 表示道路的数量，$n,m(1≤n≤1000，0≤m≤ 10000)$ 。

接下来 $m$ 行每行包含一对整数 $a,b$ 表示有一条从地点 $a$ 到地点 $b$ 的单向道路。

输出描述

输出城市中所有“菱形”的数量。

样例1

输入

4 12
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

输出

12

说明

存在 $12$ 个菱形:

$1->2->3,1->4->3$

$1->2->4,1->3->4$

$2->3->1,2->4->1$

$4->2->1,4->3->1$

$4->1->2,4->3->2$

$4->1->3,4->2->3$

样例2

输入

5 4
1 2
2 3
1 4
4 3

输出

1

说明

存在 $1$ 个菱形：

$1->2->3,1->4->2->3$