알고리즘 random 시간복잡도 O(TKN2)O(TKN2) 풀이 ii번 정점과 jj번 정점 사이의 인접 연결 정보를 저장한 행렬을 AA, ii번 정점과 jj번 정점 사이 거리가 2인 연결 정보를 저장한 행렬을 BB라 하면 A2=BA2=B인지 아닌지를 확인하면 된다. 그러나 일반적인 행렬 제곱 시 O(N3)O(N3)이므로 시간 제한에 걸리게 된다. Freivalds′ algorithm이라는 신박한 알고리즘이 존재한다. x∈Rn라 할 때, A2x=Bx인 경우 약 12의 확률로 A2=B이다. 이 곱셈의 시간복잡도는 O(N2)이다. random한 x에 대해 10번 확인 시 적중 확률은 99.9%이다. 코드 #include..
