서로 도달 가능한 쌍
플래티넘 V의견: 0
정점 \(N\)개와 간선 \(M\)개로 이루어진 방향 그래프가 주어진다. 서로 도달 가능한 정점들의 순서쌍 \((u, v)\) (\(u \ne v\)) 의 개수를 구하여라.
순서쌍 \((u, v)\) 가 조건을 만족한다는 것은 \(u\) 에서 \(v\) 로, 그리고 \(v\) 에서 \(u\) 로 가는 경로가 모두 존재함을 의미한다. \((u,v)\) 와 \((v,u)\) 는 서로 다른 순서쌍으로 센다.
이러한 쌍은 정확히 같은 SCC 안의 정점 쌍이다. 각 SCC의 크기를 \(s\) 라 하면 그 안에서 만들어지는 순서쌍은 \(s \cdot (s-1)\) 개이므로, 모든 SCC에 대해 합하면 된다. 값이 매우 클 수 있으므로 64비트 정수를 사용하라. 반복적 SCC 알고리즘으로 \(O(N+M)\) 에 처리하라.
\(1 \le N \le 200{,}000\)
\(0 \le M \le 500{,}000\)
\(1 \le u, v \le N\)
첫째 줄에 \(N\)과 \(M\)이 주어진다.
이후 \(M\)개의 줄에 간선 \(u \to v\) 가 주어진다.
서로 도달 가능한 정점 순서쌍의 개수를 출력한다.
5 5
1 2
2 3
3 1
3 4
4 5
6SCC는 \(\{1,2,3\}\)(크기3), \(\{4\}\), \(\{5\}\) 이다. 크기 3인 SCC가 \(3\times2=6\) 개의 순서쌍을 만들고, 나머지는 0이다. 답은 6.
4 4
1 2
2 1
3 4
4 3
4SCC는 \(\{1,2\}\), \(\{3,4\}\) 로 각각 크기 2이다. 각각 \(2\times1=2\) 쌍을 만들어 총 4쌍이다.
riseoj 작성
출처 Original
평가 및 의견
서로 도달 가능한 쌍
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
서로 도달 가능한 쌍