Biconnected Component & Cactus
Prerequisite
- Articulation Point & Bridge
- SCC (Optional)
Biconnected Component
이중연결요소는 무방향 그래프에서 정의되는 그래프에서의 정점 분할 테크닉이다.
BCC의 그룹은 다음과 같이 정의된다.
그룹의 정점들 중 하나를 제거해도 여전히 모든 정점이 연결되어 있고, 그런 정점들을 최대로 많이 모아둔 그룹
예시를 보자. 같은 색상의 정점들은 같은 BCC 그룹이다.
엄밀히 말하면 간선을 기준으로 그룹핑을 한 것이라고 볼 수 있다.
활용
필자도 BCC관련된 문제들을 많이 풀어보지 않아서 잘 모르겠지만,
그래프 문제들 자체를 이해하게 되는데도 도움이 되며, 선인장이나 단절점, 단절선과 관련된 키워드들에서 흔히 활용된다.
성질
하나의 정점이 $2$개 이상의 BCC에 속할 수 있다.
간선은 하나의 BCC에만 속하지만, 정점은 위 그림에서 볼 수 있듯이 여러 색을 가질 수 있다.
여러 색을 가지는 정점들은 여러 BCC에 속해있다.
$2$개 이상의 BCC에 속하는 정점은 단절점이다.
그렇다. 위 그림에서 $2$개 이상의 색을 가지는 정점들이 단절점이라는 것을 쉽게 확인할 수 있다.
BCC 내부에 간선이 하나라면 그 간선은 단절선이다.
BCC 내부에 간선이 하나라면 두 정점이 연결되어 있다.
따라서 그 간선이 제거되면 두 정점은 분리되므로 단절선이다.
BCC의 정점 개수가 $3$개 이상이면 모든 정점을 써서 싸이클을 이루게 할 수 있다.
아래 연습 문제에서 살펴보자.
알고리즘
여러 알고리즘이 있을 수 있으나 그 중 하나를 소개한다.
구현에서 우리가 얻으려는 것은,
- 각 정점들이 속해있는 BCC 개수
- BCC 마다 어떤 정점들이 속해있는지
- BCC 마다 어떤 간선들이 속해있는지
이다. 이 세 가지를 모두 구할 필요는 없고, 필요한 것만 적절히 구현해서 구하면 된다.
코드에선 세 개를 다 구하는 식으로 해보자.
알고리즘은 DFS 기반으로 선형 시간 $O(N)$에 구할 수 있고, SCC를 구하는 타잔 알고리즘과 유사하다.
DFS 함수는 DFS 스패닝 트리에서 부모로 가는 간선을 사용하지 않고, 현재 정점에서 도달할 수 있는 가장 이르게 방문된 간선의 dfsn을 반환한다.
현재 노드가 $u$라면, $u$에서 인접한 간선들 중, 한 번도 검사되지 않은 간선은 스택에 $(u, v)$ 형태로 삽입한다.
만약 $v$가 이미 방문된 정점이라면 $v$의 DFS 순서만 결과값에 $Min$ 연산으로 갱신해주고, 방문되지 않았다면 DFS 함수를 호출한다.
만약 $v$의 DFS 결과 방문순서가 $u$의 방문순서 이상이라면 $u$는 단절점이란 의미이므로 하나의 BCC를 찾은 것이다.
각 정점들이 몇개에 속해있는지를 쉽게 구하는 법은,
- 단절점이라면 BCC가 검출될 때, $1$을 더해준다.
- DFS를 처음 시작할 때 루트 노드가 아니라면 $1$을 더해준다.
로 쉽게 구할 수 있다.
코드
struct BCC {
int N, next_dfsn = 0;
vvi edges, bcc_v;
vi dfsn, included;
stack<pi> s;
vector<vector<pi>> bcc_e;
BCC(int N) : N(N) {
edges.resize(N);
dfsn.resize(N, -1);
included.resize(N);
}
void add_edge(int u, int v) { edges[u].pb(v), edges[v].pb(u); }
int dfs(int cur, int p) {
dfsn[cur] = next_dfsn++;
int ret = dfsn[cur];
for (int to: edges[cur]) {
if (to == p) continue;
if (dfsn[to] < dfsn[cur]) s.push({cur, to});
if (~dfsn[to]) {
ret = min(ret, dfsn[to]);
} else {
int tmp = dfs(to, cur);
ret = min(ret, tmp);
if (tmp >= dfsn[cur]) {
included[cur]++;
vector<pi> bcc_tmp;
bcc_v.emplace_back();
while (1) {
bcc_tmp.pb(s.top());
bcc_v.back().pb(bcc_tmp.back().fi);
bcc_v.back().pb(bcc_tmp.back().se);
s.pop();
if (bcc_tmp.back() == mp(cur, to)) break;
}
uniq(bcc_v.back());
bcc_e.pb(bcc_tmp);
}
}
}
return ret;
}
void build() {
for (int i = 0; i < N; i++) if (dfsn[i] == -1) dfs(i, -1); else included[i]++;
}
};
선인장
선인장 그래프란, 정의에 따라 정점이나 간선이 최대 $1$개의 싸이클에만 포함되는 연결 그래프이다.
이걸 정점 선인장과 간선 선인장이라 하자.
예를 들어, 다음과 같은 그래프는 간선 선인장이고,
이런 그래프는 정점 선인장이다.
정점 선인장은 항상 간선 선인장이다. 역은 성립하지 않는다.
간선이 $2$개의 싸이클에 포함된다고 하자. 그럼 그 간선을 이루는 두 정점 $\overline{u,v}$ 는 $2$개의 싸이클에 포함이 되어야해서 모순이다. $\square$
이 문제는 정점 선인장 판별이다.
BCC들을 모두 찾고, 그 BCC의 정점 개수가 $3$개 이상이라 싸이클이 생긴다면 간선의 개수가 정점의 개수와 동일한지 확인해주자.
이후 $2$번 예제를 살펴보면, 다음과 같은 그래프이다.
보면 $3$번 정점이 두 개의 싸이클에 포함이 되어있음을 알 수 있다.
앞선 검사로는 이 케이스를 검사하지 못하므로, 단절점들 중, 싸이클을 이루는 두 개 이상의 BCC에 속하는 단절점이 있다면 선인장이 아니다.
문제의 입력이 연결 그래프이므로 그 외의 경우는 모두 선인장이다.
이 문제는 간선 선인장 문제이다.
간선 선인장은 정점 선인장에서 각 단절점이 싸이클 $2$개 이상에 속해있으면 안된다는 검사를 제거하면 된다.
그저 정점이 $3$개 이상인 각 BCC의 간선 수와 정점 수가 동일한지만 판별하면 된다.
지문이 뭐라뭐라 하는데, 결국 스패닝 서브선인장을 만들기 위해서는 싸이클이 있는(정점이 $3$개 이상인) BCC 내부에 정점이 $v$개라면, $(v+1)$ 개를 정답에 곱해주는 것으로 경우의 수를 셀 수 있다.
연결 그래프가 아니거나 간선 선인장이 아니라면 $0$을 출력하고, 그렇지 않다면 위와 같이 정답을 구해서 출력한다.
정답에 큰 수 연산을 써야한다 -.-
연습 문제
정점들 중 $2$개 이상의 BCC에 속한 것들이 단절점이다.
void solve() {
int n, m;
cin >> n >> m;
BCC bcc(n);
while (m--) {
int u, v;
cin >> u >> v;
u--, v--;
bcc.add_edge(u, v);
}
bcc.build();
vi ans;
for (int i = 0; i < n; i++) if (bcc.included[i] > 1) ans.pb(i + 1);
cout << sz(ans) << endl;
sort(all(ans));
for (int i: ans) cout << i << ' ';
}
BCC중, 한 개의 간선만 포함하는($=2$개의 정점만 가지는) BCC들에 있는 간선이 단절선이다.
void solve() {
int n, m;
cin >> n >> m;
BCC bcc(n);
while (m--) {
int u, v;
cin >> u >> v;
u--, v--;
bcc.add_edge(u, v);
}
bcc.build();
vector<pi> ans;
for (int i = 0; i < sz(bcc.bcc_v); i++) {
if (sz(bcc.bcc_v[i]) == 2) {
ans.pb({bcc.bcc_v[i][0] + 1, bcc.bcc_v[i][1] + 1});
if (ans.back().fi > ans.back().se)
swap(ans.back().fi, ans.back().se);
}
}
cout << sz(ans) << endl;
sort(all(ans));
for (auto [a, b]: ans) cout << a << ' ' << b << endl;
}
$n$개의 노드와 $m$개의 간선이 있고 두 정점 $(i, j)$ 사이엔 최대 하나의 간선만 있고, 자신에게 가는 간선은 없다.
그래프 $G$의 선형 배열 구조는 모든 서로 다른 두 정점이 항상 연속된 간선으로 이어지는 경우이다.
각 테스트 케이스에 대해 다음과 같은 것들을 찾아라.
- 제거하면 $G$ 가 분리되는 정점의 개수
- 제거하면 $G$ 가 분리되는 간선의 개수
- BCC 의 개수
- BCC 내 간선 개수의 최대
Comments