整体思路是枚举三元环，其度数为 \(deg_i+deg_j+deg_k-6\) 再取 \(\min\)。全部的复杂度集中在枚举三元环上。
方法一： 枚举三个点，检查其是否成环。采用哈希表记录边的情况下，复杂度为 \(O(n^3)\)。
方法二： 从边的角度考虑。对于无向边 \((i,j)\)，改为指向度数大的点的有向边（相同度数则指向编号大的）。枚举点 \(i\) 和与 \(i\) 相连的点 \(j\)，因为有 \(m\) 条边，这一步复杂度为 \(O(m)\)；枚举点 \(j\) 的出边，可以证明不会超过 \(\sqrt{2m}\) 条边，所以这一步复杂度为 \(m\sqrt{m}\)。
证明如下：假设 \(i\) 的出边为大于 \(\sqrt{2m}\)，则原始无向图中 \(i\) 的度数大于 \(\sqrt{2m}\)，则 \(i\) 指向的 \(\sqrt{2m}\) 个 \(j\) 的度数也大于 \(\sqrt{2m}\)，总度数大于 \(2m\)，但总度数应该等于 \(2m\)，矛盾。
golang 的 map 的 key 必须是定义了相等/不等的类型，这里的 []int 就不符合要求，但是可以对于定义成 []map[int]struct{}。
方法一的 AC 代码：
func minTrioDegree(n int, edges [][]int) int {
deg := make([]int, n)
g := make([][]int, n)
for i := 0; i < n; i++ {
g[i] = make([]int, n)
}
for _, edge := range edges {
u := edge[0] - 1
v := edge[1] - 1
deg[u]++; deg[v]++
g[u][v], g[v][u] = 1, 1
}
ans := 0x3f3f3f3f
for _, edge := range edges {
u := edge[0] - 1
v := edge[1] - 1
for i := 0; i < n; i++ {
if g[i][u] == 1 && g[i][v] == 1 {
ans = min(ans, deg[i] + deg[u] + deg[v] - 6)
}
}
}
if ans == 0x3f3f3f3f {
return -1
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}