Subject
Articulation Point, 단절점.
Articulation Point, 단절점.
1) 단절점(articulation point)이란 무엇인가?
단절점이란, 그래프를 이루는 node 중에서 제거하면 연결요소가 증가하는 점이다. 연결요소란 edge로 연결되어 있는 node들의 집합이므로, 연결 요소가 증가하였음은 곧 하나의 연결요소가 해당 노드의 부재로 인해서 분해되었음을 의미한다. 즉 단절점이란 그래프의 약한 연결고리라 할 수 있다.
2) boj 11266 in C++.
문제풀이의 핵심 아이디어는 ‘색칠하기’ 이다. 그래프를 DFS를 이용하여 탐색하면서 색을 칠한다. 이후 이 색을 바탕으로 해당 노드가 단절점인지 아닌지 판단한다. 단절점 판별은 루트노드와 비 루트노드, 두 가지 경우로 나눠서 판단한다. 여기서 루트 노드는 탐색을 시작하는, 연결요소의 탐색 진입 노드를 뜻한다.
방문하지 않은 점을 시작(root)로 하여 dfs를 수행한다. 기본적으로 깊이가 더해가면 갈수록 더욱 짙은 색으로 칠하는데, 이후 자식 노드의 색과 자신의 색을 비교하여 보다 옅은 색(즉 보다 부모에 가까운 색)을 취한다. 만일 자식과의 색 비교 결과, 나보다 옅은 색을 가진다면, 이는 사이클의 존재를 암시한다. 부모보다 옅은 색을 갖기 위해서는 자식으로 조부모 이상의 노드를 가져야 하기 때문이다.
기본적으로 비 루트노드의 경우, 단절점이다. 하지만, 탐색의 결과 자식 노드의 색이 자신보다 옅다면(값이 낮다면) 이는 탐색의 결과 사이클의 존재를 암시한다. 그리고 사이클의 일부인 노드는 단절점이 될 수 없다.
루트 노드의 경우, 인접한 색의 개수가 하나보다 크다면, 이는 즉 해당 노드를 중심으로 잠재적인 연결 요소가 다수 존재함을 뜻하는 것으로, 해당 노드가 제거되면 여러 연결 요소가 발생함을 뜻한다. 루트 노드의 경우, 사이클의 일부가 되는 경우는 자연스레 제외되는데, 사이클의 일부라면 인접한 노드의 색이 모두 같기 때문이다.
/*
boj 11266, 단절점.
단절점이란 제거하면 해당 그래프에 연결요소의 개수가 증가하는 점.
즉 일종의 약한 연결고리.
해당 문제는 주어진 그래프를 탐색하여 단절점을 찾는 문제임.
*/
#include <iostream>
#include <memory.h>
#include <vector>
int V, E, cnt = 0, curTime = 1;
int arrival[100001];
std::vector<int> graph[100001];
bool isArticulationPoint[100001];
int DFS(int curNode, bool isRoot) // 이미 이전에 도달했던 노드를 만난다면 cycle의 일부요, 단절점이 아님.
{
arrival[curNode] = curTime++; // 기본적으로 depth가 늘어날수록 짙은 색(큰 값)을 취한다.
int curColor = arrival[curNode];
int adjColorCnt = 0; // 인접한 서로다른 색의 수가 2 이상이면, 무조건 단절점이다.
for (int i = 0; i < graph[curNode].size(); ++i)
{
int nextNode = graph[curNode][i];
if (arrival[nextNode] == 0) // 미방문 노드의 경우
{
adjColorCnt++;
int nextColor = DFS(nextNode, false); // 자식 노드의 색
curColor = std::min(curColor, nextColor);
// 루트 노드가 아닌 경우에 대한 단절점 판단.
if (!isRoot && nextColor >= arrival[curNode] && !isArticulationPoint[curNode])
{
// 자식 노드의 색이 부모보다 옅다면 이는 cycle의 일부임
cnt++;
isArticulationPoint[curNode] = true;
}
}
else // dfs의 결과 이미 탐색한 점을 거친다. 즉 cycle이 존재함을 뜻한다.
{
// 해당 사이클이 다른 연결요소의 일부인지 판단함.
// 부모보다 더 옅은 색의 경우는 다른 연결요소의 일부임을 뜻함.
curColor = std::min(curColor, arrival[nextNode]);
}
}
// 루트 노드에 대한 단절점 판단.
if (isRoot && adjColorCnt > 1)
{
cnt++;
isArticulationPoint[curNode] = true;
}
// 자신의 색을 반환하여 부모의 색과 비교함.
return curColor;
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
memset(arrival, 0, sizeof(arrival));
memset(isArticulationPoint, 0, sizeof(isArticulationPoint));
// 입력.
int n1, n2;
std::cin >> V >> E;
for (int i = 0; i < E; ++i)
{
std::cin >> n1 >> n2;
graph[n1].push_back(n2);
graph[n2].push_back(n1);
}
// 그래프를 이루는 모든 연결 요소들을 dfs탐색하며 색칠함.
for (int i = 1; i <= V && (curTime != V + 1); ++i)
{
if (arrival[i] == 0)
{
DFS(i, true);
}
}
// 출력
std::cout << cnt << "\n";
for (int i = 1; i <= V; ++i)
{
if (isArticulationPoint[i])
{
std::cout << i << " ";
}
}
}
C++
복사
