SCC와 다르게 무향그래프에서 사용되는 개념
ㅁ BCC
어떤 BCC안에 속한 정점 하나와 그 정점에 인접한 간선들을 지웠을 때, 그 BCC 내에 남은 정점들은 모두 연결됨.
(SCC와 유사, 하지만 간선끼리 묶어서 분류)
한번의 dfs로 BCC를 분류할 수 있다.
<코드1>
int n, m, vst[MAX], counter;
vector<int> g[MAX];
vector<vector<P>> bcc; //P는 간선 표현
stack<P> s;
int makeBCC(int u, int p) {
int ret = vst[u] = counter++;
for (int v : g[u]) if (v != p) {
//아직 방문하지 않은 간선인 경우 스택에 u-v간선 넣음
if (vst[u] > vst[v]) s.push({ u,v });
//트리간선
if (vst[v] == -1) {
int subtree = makeBCC(v, u);
ret = min(ret, subtree);
//v subtree에선 u의 조상노드로 갈 수 없음 : 새 BCC 시작
if (subtree >= vst[u]) {
vector<P> temp;
while (!s.empty()) { //간선 (u,v)끼자 빼면 됨.
int x, y; tie(x, y) = s.top(); s.pop();
temp.push_back({ x,y });
if (min(x, y) == min(u, v) && max(x, y) == max(u, v)) break;
}
bcc.push_back(temp);
}
}
//역방향 간선
else ret = min(ret, vst[v]);
}
return ret;
}
<코드2>
코드1처럼 각각의 bcc에 대해 간선리스트를 저장하면 실제로 문제풀 때 메모리나 시간이 부족한 경우가 있다. 정점마다 어떤 bcc에 포함되는지에 대한 정보와, 각 bcc에 포함된 임의의 정점을 저장하는 코드.
int n, m, vst[MAX], counter;
int bccCnt, cRoot[MAX]; //bcc번호와 각 bcc에 포함되는 임의의 정점 cRoot
vector<int> g[MAX];
set<int> cn[MAX];
stack<P> s;
int makeBCC(int u, int p) {
int ret = vst[u] = counter++;
for (int v : g[u]) if (v != p) {
//아직 방문하지 않은 간선인 경우 스택에 u-v간선 넣음
if (vst[u] > vst[v]) s.push({ u,v });
//트리간선
if (vst[v] == -1) {
int subtree = makeBCC(v, u);
ret = min(ret, subtree);
//v subtree에선 u의 조상노드로 갈 수 없음 : 새 BCC 시작
if (subtree >= vst[u]) {
cRoot[bccCnt] = u; //bccCnt번째 bcc에 u정점이 반드시 포함
while (!s.empty()) {
int x, y; tie(x, y) = s.top(); s.pop();
//x,y정점이 bccCnt번 bcc에 포함
cn[x].insert(bccCnt);
cn[y].insert(bccCnt);
if (min(x, y) == min(u, v) && max(x, y) == max(u, v)) break;
}
++bccCnt;
}
}
//역방향 간선
else ret = min(ret, vst[v]);
}
return ret;
<문제>
https://www.acmicpc.net/problem/3748
<문제설명>
양방향그래프에서 크기가 홀수인 사이클에 포함되는 정점들의 개수를 구하라.
<풀이>
한 bcc에서 홀수길이의 사이클이 존재한다면 해당 bcc의 모든 정점들은 정답에 해당하고 그 외의 경우 정답에 해당하지 않는다. bcc별로 나눠서 각 bcc에 홀수길이의 사이클이 존재하는지 확인 후 모든 정점들을 체크해주면 된다.
bcc별로 dfs혹은 bfs를 하는데 항상 방문배열 등을 초기화하면 메모리/시간 초과가 날 수 있다. 항상 초기화하지 않도록 잘 조절해줘야 한다.
<코드>
const int MAX = 1e5 + 4;
int n, m, vst[MAX], fin[MAX], counter, bccCnt, cRoot[MAX], mx;
vector<int> g[MAX], cv;
set<int> cn[MAX];
stack<P> s;
bool chk[MAX], oddCycle;
void init() {
cin >> n >> m;
bccCnt = counter = 0;
mx = -1;
memset(vst, -1, sizeof(vst));
memset(chk, 0, sizeof(chk));
memset(fin, -1, sizeof(fin));
for (int i = 1; i <= n; i++) {
g[i].clear();
cn[i].clear();
}
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
}
int makeBCC(int u, int p) {
int ret = vst[u] = counter++;
for (int v : g[u]) if (v != p) {
if (vst[u] > vst[v]) s.push({ u,v });
if (vst[v] == -1) {
int subtree = makeBCC(v, u);
ret = min(ret, subtree);
if (subtree >= vst[u]) {
cRoot[bccCnt] = u;
while (!s.empty()) {
int x, y; tie(x, y) = s.top(); s.pop();
cn[x].insert(bccCnt);
cn[y].insert(bccCnt);
if (min(x, y) == min(u, v) && max(x, y) == max(u, v)) break;
}
++bccCnt;
}
}
else
ret = min(ret, vst[v]);
}
return ret;
}
void dfs(int u, int p, const int id) {
cv.push_back(u);
for (int v : g[u]) if (cn[v].find(id) != cn[v].end()) {
if (vst[v] > counter && fin[v] < id) {
if ((vst[u] - vst[v]) % 2 == 0)
oddCycle = true;
}
else if(vst[v] <= counter){
vst[v] = vst[u] + 1;
mx = max(mx, vst[v]);
dfs(v, u, id);
}
}
fin[u] = id;
}
void solve() {
init();
for (int i = 1; i <= n; i++) if (vst[i] == -1) makeBCC(i, 0);
memset(vst, -1, sizeof(vst));
counter = -1;
for (int c = 0; c < bccCnt; ++c) {
cv.clear(); oddCycle = 0;
vst[cRoot[c]] = counter+1;
dfs(cRoot[c], 0, c);
counter = mx;
if (oddCycle) for (int i : cv) chk[i] = true;
}
int ans = 0;
for (int i = 1; i <= n; i++) if (chk[i]) ans++;
cout << ans << '\n';
}
int main() {
FAST;
int tt; cin >> tt;
while (tt--) solve();
}
<생각>
연결관계 g와 cn을 활용해서 한 bcc에서 탐색이 이뤄지는 부분인 dfs함수를 눈여겨 보자.
ㅁ 단절점
무향그래프에서 어떤 한 점과 인접한 간선을 모두 지웠을 때 그 점이 속한 컴포넌트가 둘 이상으로 나뉘는 점.
한 번의 dfs로 모든 절단점을 출력할 수 있다.
<기본문제>
https://www.acmicpc.net/problem/11266
<설명>
어떤 임의의 점(st)에서 부터 dfs트리를 만들 때
1) u가 루트(st)인 경우 (dfs 첫 지점)
u의 자식 서브트리가 한개 이하인 경우 -> u가 없어져도 컴포넌트의 수가 줄어들지 않으므로 단절점 아님.
u의 자식 서브트리가 두개 이상인 경우 -> 무향그래프에선 교차간선이없으므로 u가 없어지면 컴포넌트의 수가 늘어날 수 밖에 없음.
2) u가 루트가 아닌경우
반드시 선조가 있음. 자식 서브트리 중 단 하나라도 u의 선조에 도달하지 못하는 서브트리가 있다면 u는 단절점
<코드>
dfs(u) : 현재 정점을 루트로 하는 서브트리에서 도달 가능한 가장 먼 선조의 번호 반환(vst가장 작은 값)
u가 전체트리의 루트인지, 루트가 아닌지에 따라 결과가 변하므로 dfs에 isRoot 파라미터 추가
부모 노드로부터 vst를 갱신하지 못하도록 p 파라미터 추가
int n, m, vst[MAX],counter;
vector<int> adj[MAX], cut;
//u에서 방문할수있는 가장 먼 선조의 방문번호
int dfs(int u, int p, bool isRoot = false) {
int ret = vst[u] = counter++;
int children = 0;
bool flag = false;
for (int v : adj[u]) {
if (v == p) continue;
if (vst[v] == -1) {
++children;
int subtree = dfs(v,u);
//자식서브트리중 하나라도 u의 선조에 도달하지 못한다면 u는 단절점
if (subtree >= vst[u]) flag = true;
ret = min(ret, subtree);
}
else
ret = min(ret, vst[v]);
}
if (isRoot && children >= 2) cut.push_back(u);
if (!isRoot && flag) cut.push_back(u);
return ret;
}
int main() {
FAST;
cin >> n >> m;
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(vst, -1, sizeof(vst));
for (int i = 1; i <= n; i++)
if (vst[i] == -1) dfs(i, 0,true);
sort(cut.begin(), cut.end());
cout << cut.size() << '\n';
for (int i : cut) cout << i << " ";
cout << '\n';
}
ㅁ 단절선
무향그래프에서 어떤 간선을 지웠을 때 컴포넌트가 늘어난다면 그 간선을 단절선, bridge, 다리, 절단선 등등으로 부른다.
단절점과 비슷한 방법으로 구할 수 있다.
<기본문제>
https://www.acmicpc.net/problem/11400
<설명>
단절선은 당연히 트리간선일 수 밖에 없다.
(만약 단절선 (u,v)가 순방향 간선이나 역방향 간선이라면 트리간선(u,v)의 존재때문에 모순이다.)
dfs 트리 상에서 u가 v의 부모일 때 v서브트리에서 u이상으로 도달할 수 있다면 (u,v)는 단절선이 아니다.
그 외의 경우, (u,v)는 단절선이다.
<코드>
dfs(u) : 현재 정점을 루트로 하는 서브트리에서 도달 가능한 가장 먼 선조의 번호 반환(vst가장 작은 값)
부모 노드로부터 vst를 갱신하지 못하도록 p 파라미터 추가
int n, m, vst[MAX], counter;
vector<int> adj[MAX];
vector<P> cut;
int dfs(int u,int p) {
int ret = vst[u] = counter++;
for (int v : adj[u]) {
if (v == p) continue;
if (vst[v] == -1) {
int subtree = dfs(v,u);
if (subtree > vst[u]) cut.push_back({ min(u,v),max(u,v) }); //사전순출력조건때문
ret = min(ret, subtree);
}
else
ret = min(ret, vst[v]);
}
return ret;
}
int main() {
FAST;
cin >> n >> m;
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(vst, -1, sizeof(vst));
dfs(1,0);//이 문제는 연결그래프. 단절점과 조건이 약간 달라서그럼
sort(cut.begin(), cut.end());
cout << cut.size() << '\n';
for (P p : cut)
cout << p.first << " " << p.second << '\n';
}<생각>
단절점 코드에서 사실 p 파라미터를 빼도 정상적으로 동작한다. 반면 단절선코드에선 그렇지 않다.
왜그런지 알게된다면 코드 수정하자.
'알고리즘 > 종만북' 카테고리의 다른 글
| DFS트리에서 간선의 종류, 사이클 검출 (0) | 2020.02.13 |
|---|---|
| WORDCHAIN - 단어제한 끝말잇기 (오일러 경로, 헤밀토니안 경로) (0) | 2020.02.12 |
| 오일러 경로 (0) | 2020.02.12 |
| DICTIONARY - 고대어 사전 (위상정렬) (0) | 2020.02.12 |
| 펜윅 트리 (0) | 2020.02.10 |