[BOJ/Gold 4] 백준 23324 어려운 모든 정점 쌍 최단 거리(C++)

문제 링크

https://www.acmicpc.net/problem/23324

23324번: 어려운 모든 정점 쌍 최단 거리

 

문제

연두는 방금 "플로이드 와샬 알고리즘"을 공부했다. 이 알고리즘은 N개의 정점으로 이루어진 그래프에서, 모든 정점 쌍의 최단 거리를 O(N3)에 구해준다. 

신이 난 연두는 자신이 좋아하는 그래프를 하나 가져왔다. 이 그래프는 N개의 정점과 M개의 양방향 간선으로 이루어진 단순 연결 그래프이며, 정점에는 1,2,…,n으로 번호가 매겨져있다. 또한 딱 하나의 간선에만 1의 가중치가 있고 나머지 간선은 가중치가 0이다.

이제 이 그래프에서 모든 정점 쌍의 최단 거리의 합을 구해보려고 한다. 즉, 1≤i<j≤N를 만족하는 모든 N(N−1)2개의 쌍 (i,j)에 대해, i번 정점과 j번 정점간의 최단거리를 전부 더한 값을 구할 것이다.

연두는 신나서 코드를 짰지만 한참 동안 기다려도 결과가 나오지 않았다. 절망에 빠진 연두는 더 좋은 방법을 생각해 냈는데, 바로 대회에 이 문제를 출제하여 여러분들이 답을 대신 구하게 하는 것이다.

입력

첫 번째 줄에 정점의 개수 N(2≤N≤100000), 간선의 개수 M(1≤M≤200000), 정수 K(1≤K≤M)가 주어진다.

다음 M개의 줄에 걸쳐 ui와 vi가 주어진다. 이것은 i번째 간선은 ui와 vi를 잇는다는 것을 의미한다. (1≤ui,vi≤n,ui≠vi)

단순 연결 그래프만 입력으로 주어지며, K번째 간선의 가중치는 1이고, 나머지 간선의 가중치는 0이다.

출력

모든 정점 쌍의 최단 거리의 합을 출력한다.

출력의 값이 32비트형 정수(C/C++의 int)의 최댓값을 넘을 수 있음에 주의하자.

예제 입력 1

5 4 2
1 2
2 3
3 4
4 5

예제 출력 1

6

각 정점 쌍에 대한 최단거리는 다음과 같다

•  1↔2 : 0
•  1↔3 : 1
•  1↔4 : 1
•  1↔5 : 1
•  2↔3 : 1
•  2↔4 : 1
•  2↔5 : 1
•  3↔4 : 0
•  3↔5 : 0
•  4↔5 : 0

예제 입력 2 복사

3 3 1
1 2
2 3
3 1

예제 출력 2 복사

0

힌트

단순 연결 그래프란 다음 조건들을 모두 만족하는 그래프를 의미한다.

• 어떤 정점 u와 다른 정점 v를 잇는 간선 u−v는 최대 한 개이다.
• 어떤 정점 u를 스스로 연결하는 간선 u−u는 존재하지 않는다.
• 어떤 정점 u에서 다른 정점 v까지 한 개 이상의 간선을 이용하여 항상 도달할 수 있다.

알고리즘 분류

• 유니온 파인드

풀이

가중치가 1인 간선은 단 하나, K번째 간선이므로, K번째 간선을 받았을 때는 유니온 파인드로 연결하지 말도록 하자.

그럼 그룹이 2개 생길 텐데, 같은 그룹 내에 있는 정점들은 정점 간 이동할 때 가중치가 0이 된다. 하지만 다른 그룹 내에 있는 정점들은 이동할 때 가중치가 1이 된다. 예를 들어, A그룹에 정점이 2개, B그룹에 정점이 3개 있으면 A그룹에 있는 정점이 B그룹의 각각의 정점으로 이동할 때 가중치의 총합은 3이 된다.

따라서 가중치가 0인 간선이라면 유니온 파인드로 묶고, 가중치가 1인 간선이라면 묶지 않는다. 이렇게 되면 그룹이 1개 아니면 2개 생기게 된다.

그룹이 1개라면 모든 정점 쌍의 최단 거리는 0이 된다.(다 같은 그룹이고, 같은 그룹끼리는 이동할 때 가중치가 0이므로)

그룹이 2개라면 모든 정점 쌍의 최단 거리는 (그룹 1의 정점 개수) X (그룹 2의 정점 개수)가 된다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9

using namespace std;
int N, M, K;
LL Cnt[MAX];
int Parent[MAX];
int Left = 0, Right = 0;
LL answer = 0;

void Init() {
	for (int i = 0; i < MAX; i++) {
		Parent[i] = i;
		Cnt[i] = 1;
	}
}

int Find(int X) {
	if (Parent[X] == X) {
		return X;
	}
	return Parent[X] = Find(Parent[X]);
}

void Union_Group(int X, int Y) {
	int P_X = Find(X);
	int P_Y = Find(Y);
	if (P_X < P_Y) {
		Parent[P_Y] = P_X;
		Cnt[P_X] += Cnt[P_Y];
		Cnt[P_Y] = 0;
	}
	else {
		Parent[P_X] = P_Y;
		Cnt[P_Y] += Cnt[P_X];
		Cnt[P_X] = 0;
	}
}

void Input() {
	Init();
	cin >> N >> M >> K;
	for (int i = 1; i <= M; i++) {
		int U, V;
		cin >> U >> V;
		if (i == K) {
			continue;
		}
		if (Find(U) != Find(V)) {
			Union_Group(U, V);
		}
	}
}

void Find_Answer() {
	for (int i = 1; i <= N; i++) {
		if (Find(i) == i) {
			if (Left == 0) {
				Left = i;
			}
			else {
				Right = i;
			}
		}
	}
	if ((Left != 0) && (Right != 0)) {
		answer = Cnt[Find(Left)] * Cnt[Find(Right)];
	}
	else {
		answer = 0;
	}
	cout << answer << "\n";
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}