백준15768 Duathlon

문제 링크

  • http://icpc.me/15768

문제 출처

  • 2018 APIO 3번

사용 알고리즘

  • BCC

풀이

N개의 정점과 M개의 무향 간선으로 이루어진 그래프가 주어집니다. s에서 c를 거쳐 f로 가는 단순 경로가 존재하는 서로 다른 세 정점 s, c, f를 선택할 것입니다. 이 조건을 만족하는 (s, c, f) 순서쌍의 경우의 수를 구하는 문제입니다.

단순 경로가 아니라는 것은 반드시 두 번 이상 지나가는 정점이 존재한다는 것을 의미합니다.
반드시 두 번 이상 지나가는 정점을 v라고 한다면, 그래프에서 v를 지웠을 때 경로가 끊어지게 됩니다. 즉, v는 단절점입니다.
그러므로 s, c, f가 모두 같은 BCC에 속한다면 조건을 만족하는 단순 경로가 존재한다는 것을 알 수 있습니다.

여사건을 생각합시다.
전체 경우의 수에서 (s와 c가 다른 BCC에 있고, c와 f가 다른 BCC에 있는 경우의 수)를 빼주면 됩니다.

주어지는 그래프가 연결 그래프가 아닐 수 있으니 주의해야 합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

int n, m;
vector<int> g[101010];
ll sz[101010];
ll dep[101010];
ll low[101010];
ll bcc_sz[101010];
ll pcnt[101010];
int st;

void getSize(int now, int prv = -1){
	sz[now] = 1;
	for(auto nxt : g[now]){
		if(prv == nxt) continue;
		if(sz[nxt]) continue;
		getSize(nxt, now);
		sz[now] += sz[nxt];
	}
}

ll dfs(int now, int prv = -1){
	ll ret = 0, cnt = 1; bcc_sz[now] = 1;
	if(prv == -1) dep[now] = 1;
	else dep[now] = dep[prv] + 1;
	low[now] = dep[now];
	for(auto nxt : g[now]){
		if(nxt == prv) continue;
		if(dep[nxt]){
			low[now] = min(low[now], dep[nxt]); continue;
		}
		ret += dfs(nxt, now);
		low[now] = min(low[now], low[nxt]);
		if(low[nxt] < dep[now]){ //same bcc
			bcc_sz[now] += bcc_sz[nxt];
			pcnt[now] += pcnt[nxt];
		}else{ //articulation point
			cnt += sz[nxt];
		}
	}
	pcnt[now] += cnt * (cnt-1);
	if(prv != -1 && low[now] >= dep[prv]){ //par == articulation point
		ret += bcc_sz[now] * (pcnt[now] + (sz[st] - sz[now]) * (sz[st] - sz[now] - 1));
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i=0; i<m; i++){
		int a, b; cin >> a >> b;
		g[a].push_back(b); g[b].push_back(a);
	}
	ll ans = 0;
	for(int i=1; i<=n; i++){
		if(sz[i]) continue;
		st = i; getSize(i);
		ans += sz[i] * (sz[i] - 1) * (sz[i] - 2) - dfs(i);
	}
	cout << ans;
}