[C++] 11400번 단절선 - 그래프 이론, 그래프 탐색, DFS, 단절점과 단절선

#include <iostream>
#include <vector>
#include <algorithm>

#define FOR(i, k, N) for(int i=k; i<=N; i++)
#define Fi first
#define Se second

using namespace std;

const int MAX_V = 100001;  //최대 정점의 개수
const int MAX_E = 1000001;  //최대 간선의 개수

vector<int> Vertex[MAX_E];  //트리
int discovered[MAX_V], cnt;  //dfs 스패닝 트리에서 발견된 순서
vector<pair<int, int>> isCutEdge;  //절단선인가?
int V, E;  //정점의 개수 V, 간선의 개수 E

void input()
{
    cin >> V >> E;
    FOR(i, 1, E) {
        int a, b;  cin >> a >> b;
        Vertex[a].push_back(b);
        Vertex[b].push_back(a);
    }
}

int dfs(int no, int par)
{
    discovered[no] = ++cnt;  //발견된 순서(1부터 시작)
    int ret = discovered[no];
    
    FOR(i, 1, Vertex[no].size()) {
        int next = Vertex[no][i-1];  //탐색할 노드
        
        if(next == par)
            continue;
        
        if(!discovered[next]) {  //탐색이 아직 되지 않았으면
            int subtree = dfs(next, no);
            if(subtree > discovered[no])  //dfs를 했을 때 하위로 발견되는 노드들의 ret가 더 크다면
                isCutEdge.push_back({min(next, no), max(next, no)});  //단절선에 추가
            ret = min(ret, subtree);
        }
        else
            ret = min(ret, discovered[next]);
    }
    
    return ret;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    
    input();
    
    dfs(1, 0);
    
    sort(isCutEdge.begin(), isCutEdge.end());
    
    cout << isCutEdge.size() << '\n';
    FOR(i, 1, isCutEdge.size())
        cout << isCutEdge[i-1].Fi << ' ' << isCutEdge[i-1].Se << '\n';
                
    return 0;
}

알고리즘은 다른 블로그에서 자세하게 다루고 있어서 생략한다.

 

이렇게 문제 별로 나누면 알고리즘을 정리할 수가 없어서 언젠가는 알고리즘을 체계적으로 정리해야 하는데 솔직히 나는 아직 그 정도의 수준이 안된다고 생각하기 때문에...

 

나중에 다이아를 찍게 된다면 이론 글도 하나씩 작성하려고 한다.

 

 

 

 

 

 

<단절점과 단절선>

https://jason9319.tistory.com/m/119

단절점(Articulation Point)와 단절선(Bridge)

 

 

 

 

 

 

 

 

 

 

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.