코딩캠프/BOJ
[11266] 단절점
by 코곰_
2024. 2. 21.
// 11266 단절점
// 시작점이 어디인지 무관하다!
#include<iostream>
#include<cstdio>
#include<vector>
#include<string.h>
#include<algorithm>
#define MAX_N 100001
using namespace std;
vector<int>adjList[MAX_N];
int order[MAX_N];
bool isCut[MAX_N];
int T, number;
// 단절점 탐색
int dfs(int here, bool isRoot) {
order[here] = number++; // DFS 탐색 순서 저장
int low = order[here]; // low 의 초기값은 자기 자신의 order
int child = 0; // 자식 수 count
for (int next : adjList[here]) {
if (order[next] > 0) {
low = min(low, order[next]);
continue;
}
child++;
int minValue = dfs(next, false);
if (!isRoot && order[here] <= minValue) { // root값 확인
isCut[here] = true;
}
low = min(low, minValue); //
}
if (isRoot) {
isCut[here] = (child >= 2);
}
return low;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int V; // 정점 수
int E; // 간선 수
scanf("%d %d", &V, &E);
for (int i = 1; i <= V; i++) {
adjList[i].clear();
}
memset(order, 0, sizeof(order));
memset(isCut, 0, sizeof(isCut));
for (int i = 0; i < E; i++) {
int from;
int to;
scanf("%d %d", &from, &to);
adjList[from].push_back(to);
adjList[to].push_back(from); // 양방향
}
number = 1;
for (int i = 1; i <= V; i++) {
if (order[i] == 0) {
dfs(i, true);
}
}
vector<int> res;
int cnt = 0;
for (int i = 1; i <= V; i++) {
if (isCut[i]) {
cnt++;
res.push_back(i);
}
}
printf("%d\n", cnt); // 단절점 개수
for(int x: res){
printf("%d ", x);
}
}