一、题意转化

给定 $N$ 个点、$M$ 条边的无向简单图（无自环、无重边）。

对无序点对 $(A,B)$（$A<B$），它是“间接朋友”当且仅当同时满足：

1. $A,B$ 不相邻（不是直接朋友）；
2. $A,B$ 至少有一个公共邻居 $C$（即存在 $C$ 使 $A-C$、$B-C$ 都是边）。

所以本题等价于：统计图中“最短距离恰好为 2”的点对个数。

注意条件 2 是“存在性”——有多个公共邻居也只算一对。

二、思路分析

观察 1：$N\le 500$，邻接矩阵完全够用

判断“两点是否相邻”需要 $O(1)$ 查询，用 adj[u][v] 最合适。空间 $500\times500$ 仅约 250 KB，用 char/bool 存更省。

观察 2：直接按定义枚举即可

枚举所有 $i<j$（共 $\frac{N(N-1)}{2}\le 124750$ 对），对每一对：

• 若 adj[i][j]==1 → 直接朋友，跳过；
• 否则枚举 $k=1..N$，只要发现 adj[i][k] && adj[j][k]，答案加一并立刻 break。

最坏时间 $O(N^3)\approx 6\times10^7$ 次基本操作，C++ 约 0.1~0.3 s，能过。稀疏图上因为 break 提前退出，实际远快于上界。

观察 3：不能“数公共邻居个数再除 2”

有人会想到用邻接矩阵平方 $C=A^2$，其中 $C_{ij}$ 是 $i,j$ 的公共邻居数量。但题目要求的是“是否存在”，不是“有多少条长度为 2 的路径”。所以判 $C_{ij}>0$ 即可，千万不要把 $C_{ij}$ 累加进答案。

观察 4：进阶写法（可选）

把每一行压成 bitset，公共邻居存在性 = (b[i] & b[j]).any()，一次位运算处理 64 位，复杂度降到 $O(N^3/64)$，$N$ 到几千也能过。

三、算法步骤

1. 读入 $N,M$；初始化 $(N+1)\times(N+1)$ 的邻接矩阵为 0；
2. 读入 $M$ 条边，令 adj[u][v]=adj[v][u]=1（$M=0$ 时此步不执行，程序仍正常输出 0）；
3. ans = 0，双重循环 $i\in[1,N],\ j\in[i+1,N]$：
   • if (adj[i][j]) continue;
   • 内层循环 $k\in[1,N]$，若 adj[i][k] && adj[j][k] 则 ans++, break;
4. 输出 ans。

四、复杂度

五、易错点

六、参考代码

版本一：邻接矩阵暴力（推荐，首选提交）

#include <bits/stdc++.h>
using namespace std;

/*
 * 题意：给定 N 个点 M 条边的无向简单图，求无序点对 (A,B) 的个数，
 *       满足 A、B 之间没有边，且至少存在一个公共邻居 C。
 *
 * 做法：邻接矩阵 + 三重循环枚举 (i, j, k)。
 * 复杂度：时间 O(N^3)（找到公共邻居即 break），空间 O(N^2)。
 */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;      // 处理空输入

    // adj[u][v] == 1 表示 u、v 是直接朋友；用 char 省空间
    vector<vector<char>> adj(n + 1, vector<char>(n + 1, 0));
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u][v] = adj[v][u] = 1;
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (adj[i][j]) continue;     // 直接朋友不计入
            for (int k = 1; k <= n; k++) {
                if (adj[i][k] && adj[j][k]) {   // 存在公共邻居 k
                    ans++;
                    break;                      // 只算一次，立即跳出
                }
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

版本二：bitset 加速（常数更小，数据加强时备用）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;

/*
 * 做法：把每个点的邻居压成 bitset，
 *       (b[i] & b[j]).any() 即表示 i、j 有公共邻居。
 * 复杂度：时间 O(N^3 / 64)，空间 O(N^2 / 8)。
 */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<bitset<MAXN>> b(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        b[u].set(v);
        b[v].set(u);
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (!b[i].test(j) && (b[i] & b[j]).any())   // 无边 & 交集非空
                ans++;
        }
    }

    cout << ans << '\n';
    return 0;
}

七、样例与自测

官方样例

输入：
4 4
1 2
2 3
3 4
1 4

输出：
2

说明：间接朋友为 $(1,3)$（公共邻居 2、4）和 $(2,4)$（公共邻居 1、3），各只算一次。

手算验证用例

3 0                        → 0   （无边）
3 2                        → 1   （链 1-2-3，只有 (1,3)）
1 2
2 3
4 3                        → 3   （星形图，叶子两两配对）
1 2
1 3
1 4
5 4                        → 3   （链 1-2-3-4-5：(1,3)(2,4)(3,5)）
1 2
2 3
3 4
4 5
4 6                        → 4   （完全图 K4 补 0 对，再加孤立点也不变）
1 2
1 3
1 4
2 3
2 4
3 4