백준11622 Juice Junctions

문제 링크

  • http://icpc.me/11622

문제 출처

  • 2015 CERC J번

사용 알고리즘

  • BCC
  • Hashing

풀이

여름학교 그래프 실습 때 tricon이라는 문제가 있었습니다. 친구에게 풀이를 들었지만 업솔빙이 끝날 때까지 결국 못 풀어서 다음날 조교님께 출처를 어쭈어봤고, 바로 이 문제였습니다.
근데 Juice Junctions 문제가 tricon보다는 훨씬 어려우니 먼저 tricon이라는 문제부터 봅시다.

tricon 문제

두 정점을 잇는 경로에서 임의의 한 간선을 제거해도 두 정점이 연결되어있다면 두 정점을 bi-connected라고 한다.
만약 두 정점을 잇는 경로에서 임의의 한 간선을 제거해도 두 정점이 bi-connected하면 두 정점을 tri-connected라고 하자.
그래프가 주어지면 tri-connected 관계인 정점의 쌍의 개수를 출력하라.
|V| <= 3000, |E| <= 4500

tricon 풀이

주어진 그래프 G에서 임의의 간선 하나를 없앤 새로운 그래프 G2를 생각해봅시다.
G2에서 bi-connected한 두 정점은 tri-connected관계일 가능성이 있습니다.
G2에서 두 정점이 bi-connected한지 판단하는 것은 G2의 단절선을 모두 제거한 그래프에서 두 정점이 연결되어있는지 확인하면 됩니다.

어떤 두 정점이 임의의 간선을 없앤 총 |E| 개의 새로운 그래프에서 모두 bi-connected하다면 그 두 개의 정점은 tri-connected합니다.

|E| 개의 새로운 그래프에서 단절선들을 모두 제거했을 때, 각 정점이 어떤 컴포넌트에 속하는지 기록을 해두자. 그러면 각 정점마다 |E| 개의 기록이 남아있습니다.
두 개의 정점에 존재하는 각각 총 |E| 개의 기록을 해싱등을 이용해 비교하면 tri-connected인지 빠르게 확인할 수 있습니다.

Juice Junctions

다시 Juice Junctions문제로 돌아옵시다. 모든 정점 쌍에 대해서 max-flow를 구해서 모두 더한 값을 출력하라고 합니다. 각 정점의 차수는 최대 3이므로 max-flow도 최대 3입니다.
max-flow를 구하는데 O(N)이 걸립니다. 모든 정점 쌍에 대해 이를 수행하면 O(N3), 너무 느리죠.

min-cut max-flow theorem에 의하면 min-cut과 max-flow는 같습니다. min-cut을 구하는 것으로 생각해봅시다.

연결되어있지 않은 정점 사이의 min-cut은 0입니다. 그러므로 각 컴포넌트들은 분리해서 생각해도 됩니다.
이 그래프에서는 어떤 두 정점을 잡아도 min-cut은 최소 1입니다.

tricon 문제와 비슷하게 단절선을 모두 제거해봅시다.

단절선을 제거해서 분리되는 두 정점 사이의 min-cut은 1이라는 사실을 알 수 있습니다.
단절선을 제거해서 생기는 컴포넌트들은 분리해서 생각해봅시다.


이 그래프에서는 어떤 두 정점을 잡아도 min-cut은 2 이상입니다. 아까 위에서 min-cut은 최대 3이라는 것을 알아냈기 때문에, min-cut이 2인지 3인지만 판단하면 됩니다.
tricon 문제에서 했던 것처럼 임의의 간선 하나를 없애고, 각 BCC마다 번호를 1, 2, …로 매겨줍시다.

다른 간선도 없애봅시다.

모든 간선에 대해 이 작업을 반복하면 tricon 문제처럼 tri-connected관계인 정점들을 찾아낼 수 있습니다.
그리고, tri-connected인 두 정점 사이의 min-cut이 3입니다.

결국, 두 정점이 tri-con이라면 min-cut은 3이 되고, bi-con이라면 2, 그냥 연결이 되어있다면 1, 연결이 되어있지 않다면 0입니다.

잘 구현해주면 됩니다.

전체 코드

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll mod = 1e9+7;
ll p = 917;

vector<int> g[3030];
vector<int> g2[3030]; //graph without bridge
int n, m;
int pv;

int com[3030], bicom[3030], tricom[3030];
int chk[3030], dfn[3030], low[3030];

ll num[3030]; //hashing - tricon

void dfs_com(int v){
	for(auto i : g[v]){
		if(com[i] == 0){
			com[i] = com[v];
			dfs_com(i);
		}
	}
}

void component(){
	int pv = 0;
	memset(com, 0, sizeof com);
	for(int i=1; i<=n; i++){
		if(com[i] == 0){
			com[i] = ++pv;
			dfs_com(i);
		}
	}
}

void findBridge(int v, int prv){
	chk[v] = 1;
	dfn[v] = ++pv;
	low[v] = ++pv;
	for(auto i : g[v]){
		if(i == prv) continue;
		if(chk[i] == 2) g2[v].push_back(i);
		else if(chk[i] == 1){
			low[v] = min(low[v], dfn[i]);
			g2[v].push_back(i);
		}else if(chk[i] == 0){
			findBridge(i, v);
			if(low[i] <= dfn[v]){
				g2[v].push_back(i);
				g2[i].push_back(v);
			}
		}
		low[v] = min(low[v], low[i]);
	}
	chk[v] = 2;
}

void dfs_bi(int v){
	for(auto i : g2[v]){
		if(bicom[i] == 0){
			bicom[i] = bicom[v];
			dfs_bi(i);
		}
	}
}

void removeBridge(){
	pv = 0;
	for(int i=1; i<=n; i++) g2[i].clear();
	memset(chk, 0, sizeof chk);
	for(int i=1; i<=n; i++) if(chk[i] == 0) findBridge(i, 0);
}

void bicomponent(){
	memset(bicom, 0, sizeof bicom);
	removeBridge();
	int pv = 0;
	for(int i=1; i<=n; i++){
		if(bicom[i] == 0){
			bicom[i] = ++pv;
			dfs_bi(i);
		}
	}
}

void dfs_tri(int v){
	for(auto i : g2[v]){
		if(tricom[i] == 0){
			tricom[i] = tricom[v];
			dfs_tri(i);
		}
	}
}

void tricomponent(){
	memset(tricom, 0, sizeof tricom);
	removeBridge();
	int pv = 0;
	for(int i=1; i<=n; i++){
		if(tricom[i] == 0){
			tricom[i] = ++pv;
			dfs_tri(i);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i=0; i<m; i++){
		int s, e; cin >> s >> e;
		g[s].push_back(e);
		g[e].push_back(s);
	}
	component();
	bicomponent();

	for(int i=1; i<=n; i++){
		for(int x=0; x<g[i].size(); x++){
			int j = g[i][x];
			if(i > j) continue;

			swap(g[i][x], g[i].back());
			g[i].pop_back();

			for(int k=0; k<g[j].size(); k++){
				if(g[j][k] == i){
					g[j].erase(g[j].begin() + k);
					break;
				}
			}

			tricomponent();
			for(int k=1; k<=n; k++){
				num[k] = (num[k] * p + tricom[k]) % mod;
			}
			g[i].push_back(j);
			g[j].push_back(i);
			swap(g[i][x], g[i].back());
		}
	}

	ll ans = 0;
	for(int i=1; i<=n; i++){
		for(int j=i+1; j<=n; j++){
			if(num[i] == num[j]) ans += 3;
			else if(bicom[i] == bicom[j]) ans += 2;
			else if(com[i] == com[j]) ans++;
		}
	}
	cout << ans << "\n";
}