본문 바로가기
코딩캠프/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);
	} 
}

'코딩캠프 > BOJ' 카테고리의 다른 글

[11659] 구간합 구하기4  (0) 2024.02.22
[11051] 이항계수2  (0) 2024.02.22
[11050] 이항계수 1  (1) 2024.02.21
[1010] 다리놓기  (0) 2024.02.21
[11657] 타임머신  (0) 2024.02.20