개발 코어 강화 일지

문제 23324번: 어려운 모든 정점 쌍 최단 거리 첫 번째 줄에 정점의 개수 $N$($2 \le N \le 100\,000$), 간선의 개수 $M$($1 \le M \le 200\,000$), 정수 $K$($1 \le K \le M$)가 주어진다. 다음 $M$개의 줄에 걸쳐 $u_i$와 $v_i$가 주어진다. 이것은 $i$번째 간선은 $u_i$ www.acmicpc.net 풀이 크루스칼 알고리즘을 돌리면 N이 최대 100,000이므로 반드시 시간초과 O(N3)가 난다. K번째 간선을 정점 X와 정점 Y를 연결하는 간선이라고 하자. 문제에서 X-Y 간선만 가중치가 1이므로 이 간선을 우선 제외해보고 문제에 접근해 보자. 정점 X와 연결된 정점의 개수를 cntX, Y와 연결된 정점의 개수를 cntY라고 하..