图论：合适的环
4979. 合适的环 - AcWing题库
给定一个 n 个点 m 条边的无向图。
图中不含重边和自环。
请你在图中选出一个由三个点组成的环。
设图中一共有 x 条边满足：不在选择的环内，且与选择的环内某个点相连。
我们希望通过合理选环，使得 x 的值尽可能小。
请你输出 x 的最小可能值。
输入格式
第一行包含两个整数 n,m。
接下来 m 行，每行包含两个整数 a,b，表示点 a和点 b 之间存在一条无向边。
输出格式
如果存在满足条件的环，则输出 x 的最小可能值。
否则，输出
-1。数据范围
前 33 个测试点满足 3≤n≤10，0≤m≤10。
所有测试点满足 3≤n≤4000，0≤m≤4000，1≤a,b≤n，a≠。输入样例1：
5 6 1 2 1 3 2 3 2 4 3 4 4 5输出样例1：
2样例1解释
给定图中，由三个点组成的环一共有两个，分别为点 1,2,3 组成的环以及点 2,3,4 组成的环。
对于点 1,2,3 组成的环，我们逐个分析每条边是否满足：不在环内，且与环内的某个点相连。
- 边 (1,2) 在环内。
- 边 (1,3 在环内。
- 边 (2,3)在环内。
- 边 (2,4)不在环内，且与点 2 相连。
- 边 (3,4)不在环内，且与点 3 相连。
- 边 (4,5)不在环内，但是与点 1,2,3 均不相连。
因此，如果选择点 1,2,3组成的环，则 x 的值为 2。
对于点 2,3,4 组成的环，我们逐个分析每条边是否满足：不在环内，且与环内的某个点相连。
- 边 (1,2) 不在环内，且与点 2 相连。
- 边 (1,3)不在环内，且与点 3 相连。
- 边 (2,3)在环内。
- 边 (2,4) 在环内。
- 边 (3,4) 在环内。
- 边 (4,5) 不在环内，且与点 4 相连。
因此，如果选择点 2,3,4组成的环，则 x 的值为 3。
综上，x 的最小可能值为 2。
输入样例2：
7 4 2 1 3 6 5 1 1 7输出样例2：
-1
图论问题，x 的表示选取的三个点各自和其他点连接成的线的数量之和（每个点排除共同形成环的另外两个点）， 通过二维数组 arr[i][j]存储点，表示点 i 和点 j 之间存在一条线，结构体 s[i]{a,b} 存储线表示 第 i 条线由点 a 和 点 b 相连，mp[i] 存储第 i 个点和几个点相连， 根据题意，外循环遍历线1-m，可通过 s 得到连接线的两个点 a，b，内循环遍历第三个点 c，通过 arr 判断三个点之间是否都存在线，形成环，然后通过 mp 得到 x，因为 mp 存储的点 i 连接的其他所有点数量，但 x 求的是形成环的三个点分别排除与另外两点之间的线的情况，所以三个点每个点排除两条，三个点排除 6 条，一共就是 6 条，就是 -6.
AC code：
#include<bits/stdc++.h> using namespace std; int arr[4010][4010]; int n, m; struct s { int a, b; } s[4010]; unordered_map<int, int> mp; int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; s[i] = {a, b}; arr[a][b]++; arr[b][a]++; mp[a]++, mp[b]++; } int ans = 2e9; for (int i = 1; i <= m; i++) { int a = s[i].a, b = s[i].b; // cout << a << " " << b<<endl; for (int c = 1; c <= n; c++) { if (arr[a][c] && arr[b][c]) { int res = mp[a] + mp[b] + mp[c] - 6; ans = min(res, ans); } } } if (ans != 2e9) { cout << ans; } else cout << -1; }