LC1761 一个图中连通三元组的最小度数

XYukari / 2023-09-01 / 原文

一项三元环枚举技术。

整体思路是枚举三元环，其度数为 \(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
}