[BOJ S1][C++] 백준 14675번: 단절점과 단절선

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

14675번: 단절점과 단절선

 

문제

그래프 이론에서 단절점(cut vertex)과 단절선(bridge)은 다음과 같이 정의 된다.

• 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절점이라 한다.
• 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 간선을 단절선이라 한다.

이 단절점과 단절선을 우리는 트리(tree)에서 구하려고 한다. 그래프 이론에서 트리(tree)의 정의는 다음과 같다.

• 트리(tree) : 사이클이 존재하지 않으며, 모든 정점이 연결되어 있는 그래프

트리의 정보와 질의가 주어질 때, 질의에 대한 답을 하시오. 

입력

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정보 a, b가 주어진다. 이는 a정점과 b정점이 연결되어 있다는 뜻이며, 입력으로 주어지는 정보는 트리임이 보장된다. (1 ≤ a, b ≤ N)

다음 줄에는 질의의 개수 q가 주어진다. (1 ≤ q ≤ 100,000) 다음 q줄에는 질의 t k가 주어진다. (1 ≤ t ≤ 2) t가 1일 때는 k번 정점이 단절점인지에 대한 질의, t가 2일 때는 입력에서 주어지는 k번째 간선이 단절선인지에 대한 질의이다. t가 1일 때는 (1 ≤ k ≤ n)이며, t가 2일 때는 (1 ≤ k ≤ n - 1)이다. 

출력

프로그램의 출력은 표준 출력으로 한다. q줄에 대하여 해당 질의에 대한 답을 한다. 각각은 개행으로 구분하며, 질의가 맞다면 ‘yes’를, 질의가 틀리면 ‘no’를 출력한다. 

 

풀이

단절점...? 단절선...? 꽤나 장황하고 길게 설명하고 있지만 !

결국 사이클이 존재하지 않는 트리는 모든 선이 단절선이고, 맨 마지막 노드를 제외한 모든 점이 단절점이다

 

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;


bool isArtPoint(int k, vector<vector<int>>&graph) {
    // 트리는 사이클이 없으므로 맨 끝점을 제외한 모든 정점이 단절점
    
    if(graph[k].size() >= 2)
        // 인접그래프에서 graph[k].size = 연결된 정점의 갯수
        // 연결된 정점의 갯수가 2개 이상이라면 해당 정점을 없애도 연결된 정점만큼 그래프가 생긴다 !
        return true;
    
    return false;
}

bool isArtBridge() {
    // 트리는 사이클이 없으므로 모든 간선이 단절선
    return true;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int n, a,b, q, t,k;
    cin >> n;
    vector<vector<int>> graph(n+1);
    while(--n) { // 인접그래프 만들기
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    cin >> q;
    bool ans;
    while(q--) {
        cin >> t >> k;
        
        if(t==1)
            ans = isArtPoint(k, graph);
        else // t==2
            ans = isArtBridge();
        
        if(ans)
            cout << "yes\n";
        else
            cout << "no\n";
    }
    
    return 0;
}

/*
 */