6101 : 아티큘레이션 포인트 — 단절점 찾기
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
무방향 연결 그래프가 주어집니다. 그래프에서 어떤 정점을 제거했을 때 그래프가 두 개 이상의 독립된 그래프로 나누어지게(연결 성분이 증가하게) 되는 정점을 단절점(Articulation Point) 또는 컷 버텍스(Cut Vertex)라고 부릅니다.
DFS 스패닝 트리를 탐색하여, DFS 방문 순서인 dfsn과 자식들이 갈 수 있는 최상위 노드인 low 값을 활용해 모든 단절점을 찾아 출력하십시오.
DFS 스패닝 트리를 탐색하여, DFS 방문 순서인 dfsn과 자식들이 갈 수 있는 최상위 노드인 low 값을 활용해 모든 단절점을 찾아 출력하십시오.
입력 설명
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 1,000)과 간선의 개수 M (1 ≤ M ≤ 5,000)이 주어집니다.
둘째 줄부터 M개의 줄에 무방향 간선 u v가 주어집니다.
둘째 줄부터 M개의 줄에 무방향 간선 u v가 주어집니다.
출력 설명
첫째 줄에 단절점의 수 K를 출력합니다.
둘째 줄에 단절점 정점 번호들을 오름차순으로 공백 구분하여 출력합니다. 단절점이 없다면 첫째 줄에 0만 출력합니다.
둘째 줄에 단절점 정점 번호들을 오름차순으로 공백 구분하여 출력합니다. 단절점이 없다면 첫째 줄에 0만 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 5
1 2
2 3
3 4
4 5
3 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2
2 3도움
1) 루트 노드: DFS 트리에서 자식 수가 2개 이상이면 단절점입니다.
2) 일반 노드 A: A의 자식 B에 대해, B의 서브트리에서 A의 조상으로 가는 역방향 간선이 없다면(즉,
2) 일반 노드 A: A의 자식 B에 대해, B의 서브트리에서 A의 조상으로 가는 역방향 간선이 없다면(즉,
low >= dfsn[A]) A는 단절점입니다.