1 条题解
-
0
可以枚举每条边上的两个点,作为路径中间的两个点,那么只需要计算两个点的度相乘的结果即可。(需要去掉和边的另一个端点相连的度,因此度数需要减1)
核心代码
#include <bits/stdc++.h> using namespace std; const int MAXN = 10005; const int MAXM = 100005; int n, m, u[MAXM], v[MAXM], deg[MAXN]; long long ans; int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> u[i] >> v[i]; deg[u[i]]++; deg[v[i]]++; } for (int i = 1; i <= m; i++) ans += (deg[u[i]] - 1) * (deg[v[i]] - 1) * 2; cout << ans; return 0; }
- 1
信息
- ID
- 898
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 20
- 已通过
- 11
- 上传者