알고리즘 random 시간복잡도 $O(TKN^2)$ 풀이 $i$번 정점과 $j$번 정점 사이의 인접 연결 정보를 저장한 행렬을 $A$, $i$번 정점과 $j$번 정점 사이 거리가 2인 연결 정보를 저장한 행렬을 $B$라 하면 $A^2 = B$인지 아닌지를 확인하면 된다. 그러나 일반적인 행렬 제곱 시 $O(N^3)$이므로 시간 제한에 걸리게 된다. $Freivalds' \space algorithm$이라는 신박한 알고리즘이 존재한다. $x \in \mathbb{R}^n$라 할 때, $A^2 x = Bx$인 경우 약 $\frac{1}{2}$의 확률로 $A^2=B$이다. 이 곱셈의 시간복잡도는 $O(N^2)$이다. random한 $x$에 대해 10번 확인 시 적중 확률은 99.9%이다. 코드 #include..
