[백준] 11400: 단절선

0. 문제 주소

 

https://www.acmicpc.net/problem/11400

11400번: 단절선

 

 

1. 풀이

 

[PS/BFS & DFS] - [BOJ] 11266: 단절점과 다른 점은 다음과 같다.

 

1. 루트 노드인지를 체크하지 않아도 된다.

2. DFS 탐색 함수에 parent 인자를 추가한다. 이는 low를 정의할 때, 바로 직전에서 내려온 parent는 고려하지 않기 위함이다.

3. 그리고 order[curr]가 low보다 strictly 작아야 한다.

 

다른 건 다 똑같다.

 

단절점이지만 단절선은 안되는 경우를 생각해보면 이해할 수 있다.

 

 

2. 풀이 코드

 

* 유의할 점

 

 

 

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

#define MAX 100003
#define INF 987654321
#define pii pair<int, int>

using namespace std;

int V, E;
int order[MAX];
vector<int> graph[MAX];
set<pii> ans;
int cnt;

int dfs(int curr, int parent){
    order[curr] = ++cnt;
    int ret = order[curr];
    
    for (int next: graph[curr]){
        if (next == parent) continue;
        
        if (!order[next]){
            int low = dfs(next, curr);
            if (order[curr] < low) {
                int a = min(curr, next), b = max(curr, next);
                ans.insert(pii(a, b));
            }
            ret = min(ret, low);
        }
        else{
            ret = min(ret, order[next]);
        }
    } 
    
    return ret;
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    scanf("%d %d", &V, &E);
    if (V==1) {
        printf("0\n");
        return 0;
    }
    for (int i=0;i<E;i++){
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    dfs(1, 0);
    
    
    printf("%d\n", ans.size());
    for (auto it=ans.begin();it!=ans.end();it++){
        auto p = *it;
        printf("%d %d\n", p.first, p.second);
    }
    
    
    return 0;
}