1761.Minimum-Degree-of-a-Connected-Trio-in-a-Graph

我们要找一个trio，肯定要先遍历其中的一个点A。而该trio的另外两个点B和C，必然也都是A的邻接节点。所以我们在A的邻接节点集合next[A]中寻找B和C显然效率更高。但是我们似乎没有特别高效的方法直接在next[A]中找出符合条件的二元对{B,C}，只能在next[A]中用二重循环枚举B和C，再查看B和C是否是邻接的。查看B和C是否邻接，我们可以通过预处理的邻接矩阵c[x][y]来实现o(1)的查询。预先构造的邻接矩阵c[x][y]表示任意两点之间是否相邻，时间复杂度是o(E)，是可以接受的。

所以整体而言，寻找三元对{A,B,C}需要o(N^3)的大框架：

for A in range(1,n):
  for (B,C) in next[A]:
    if c[B][C]==1: 
      (A,B,C)是一个trio
      ret += inDegree[A] + inDegree[B] + inDegree[C] - 6

以上的方法会TLE。如何改进呢？我们发现，根据A找(B,C)，等价于根据B找(A,C)，根据C找(A,B)。所以整体的时间复杂度浪费了三倍。如何避免这个问题呢？解决方法是：把无向图变成有向图。也就是说，从A能找到(B,C)，但是让B不会找到(A,C)，因此我们可以令AB为单向边，即只允许A->B. 同理如果也令A->C为单向边的话，那么C就不会找到(A,B)。由这个技巧，我们可以将整体o(N^3)的复杂度降低至1/3。