단절점과 단절선
역시 솔브드 마라톤을 풀다가 단절점, 단절선 기본 문제가 나와서 공부해보았다.
문제 번호는 각각 단절점(11266), 단절선(11400)이다.
학교 알고리즘 시간에 들었던 내용이었어서 남아있던 기억이 이해하는데에 도움이 되었다.
우선 단절점이란 그래프에서 어떤 정점을 제거했을 때 그래프가 두 개 이상으로 분리되는 정점이다.
그러면 단절선은 그래프에서 어떤 간선을 제거했을 때 그래프가 두 개 이상으로 분리되는 간선이다.
아주 간단한 정의고 그러면 어떻게 효율적으로 이 점들을 찾을 수 있을까?가 알고리즘의 요지다.
나이브하게 생각을 해보면 모든 정점을 지워보며 그래프가 분리된 것이 있는지 확인하면
O(V*(V+E))의 시간이 걸리고, 단절선은 O(E*(V+E))의 시간이 걸릴 것이다.
이는 너무 많은 시간을 사용하기에 O(V+E)에 가능한 알고리즘을 알아보려고 한다.
단절점
단절점부터 생각을 해보면 어떤 점을 끊었을 때 그래프가 나눠질까?
그래프에 대해 임의의 점을 root로 잡고, DFS tree를 그려본다.
그러면 각 노드간의 조상-자식 관계가 만들어진다.
루트 정점일 때
하나밖에 없는 루트 정점이 단절점이 되기 위한 조건은 간단하다.
자식이 두 개 이상 존재하면 루트를 지웠을 때 서브 트리의 형태로 생겨나므로 그것만 판별하면 된다.
루트 정점이 아닐 때
루트가 아닌 어떤 정점 v를 지웠을 때 그래프가 나눠지지 않으려면 v를 조상으로 가지는 정점들이
맨 처음 만든 DFS 트리의 간선이 아닌 다른 간선으로 v위로 올라갈 수 있어야 한다.
이런 간선을 backedge라고 부른다.
그렇다면 v를 거치지 않고도 연결이 유지된다는 것이기 때문이다.
이제 구현을 해보자면 일반적인 DFS와 비슷한데 필요한 배열이 3개 있다.
먼저 방문한 순서를 저장하는 vis[i], 바로 위의 조상을 저장하는 par[i],
i의 서브트리에서 back edge를 통해 올라갈 수 있는 가장 작은 vis 값을 저장하는 low[i]
low[i]의 값을 업데이트하는 로직을 보면, 처음엔 low[i] = vis[i]이다.
i의 자식 j를 방문한 다음 dfs에서 돌아왔을 때
1
low[i]=min(low[i], low[j]);
이다. j가 back edge로 갈 수 있으면 i도 갈 수 있기 때문이다.
그리고 back edge (v→u)가 있으면: low[v] = min(low[v], disc[u])이다.
전체 코드로 보면
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=1;
long long a, b, c, d;
long long n, m, t, k;
long long ans=0;
cin >> n >> m;
vector<vector<int>> graph(n+1);
for(int i=0;i<m;i++){
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<int> vis(n+1, 0);
vector<int> par(n+1, 0);
vector<int> low(n+1, 1e9);
vector<int> ansv;
t=0;
function <void(int)> dfs=[&](int x){
bool cut=0;
int child=0;
t++;
vis[x]=t;
low[x]=t;
for(auto xx:graph[x]){
if(par[x]==xx)continue; //DFS로 내려온 간선은 세면 안되니까
if(!vis[xx]){
par[xx]=x;
child++;
dfs(xx);
low[x]=min(low[x], low[xx]);
if(!par[x]&&child>1)cut=1; //루트면 child>1이면 단절점이고
else if(par[x]&&low[xx]>=vis[x])cut=1;
}
else{
low[x]=min(low[x], vis[xx]);
}
}
if(cut)ansv.push_back(x);
};
for(int i=1;i<=n;i++){
if(!vis[i])dfs(i);
}
cout << ansv.size()<<'\n';
sort(ansv.begin(), ansv.end());
string sp="";
for(int i=0;i<ansv.size();i++){
cout << sp << ansv[i];
sp=' ';
}
return 0;
}
root의 단절점 판별을 위해 dfs 함수마다 child 변수를 넣었고
이제 root가 아닌 정점 v가 단절점이 되려면
1
low[xx]>=vis[x]
v의 자식 중 가장 높게 올라갈 수 있는 곳이 v보다 같거나 낮을때이다.
vis의 값은 DFS를 돌때마다 증가하므로 클수록 낮은 위치이다.
단절선
다음은 단절선인데, 이는 단절점보다 좀 더 간단하다.
root를 신경 쓸 필요가 없고, 나머지 로직은 거의 동일하다.
정점 u, v를 잇는 간선이 있을 때 단절선이 되려면
1
vis[u]<low[v]
일때이다.
단절점은 판별할 때 <= 였는데 , 왜 단절선은 <일까.
부모를 u, 자식을 v라고 정의하고, 그 이유를 알아보면
단절점에서는 v가 u까지 올라가는 경로가 있더라도 v가 사라지면 그래프는 끊어진다.
하지만 단절선에서는 v가 u까지 올라가는 경로가 있다면 v와 u사이의 선이 끊어지더라도
back edge를 통해서 v로 올라갈 수 있다는 것이다.
이 점을 캐치하지 못해서 디버깅을 계속하며 삽질을 했다.
코드로 보면
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=1;
long long a, b, c, d;
long long n, m, t, k;
long long ans=0;
cin >> n >> m;
vector<vector<int>> graph(n+1);
vector<P> ansv;
for(int i=0;i<m;i++){
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
t=0;
vector<int> vis(n+1, 0);
vector<int> par(n+1, 0);
vector<int> low(n+1, 0); //이게 x보다 낮은 애들에서 올라 갈 수 있는 최대 위치?니까
function <void(int)> dfs = [&](int x){
t++;
vis[x]=t;
low[x]=vis[x];
for(int y=0;y<graph[x].size();y++){
if(par[x]==graph[x][y])continue;
if(!vis[graph[x][y]]){
par[graph[x][y]]=x;
dfs(graph[x][y]);
low[x]=min(low[graph[x][y]], low[x]);
}
else{
low[x]=min(vis[graph[x][y]], low[x]);
}
//cout << "x: " << x << ',' << vis[x] << ' ' << "y: " << graph[x][y] << ',' <<
low[graph[x][y]] << '\n';
if(vis[x]<low[graph[x][y]]){
//cout << "x: " << vis[x] << ' ' << "y: " << low[graph[x][y]] << '\n';
ansv.push_back({min(x, graph[x][y]), max(x, graph[x][y])});
}
}
};
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i);
}
}
sort(ansv.begin(), ansv.end());
cout << ansv.size()<<'\n';
for(int i=0;i<ansv.size();i++){
cout << ansv[i].first << ' ' << ansv[i].second<<'\n';
}
return 0;
}
응용 문제들을 풀어보면서 어떻게 쓰이는지 더 자세히 알아봐야겠다.