[백준,c++] 14675번 - 단절점과 단절선

문제

14675번: 단절점과 단절선

 

코드

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>>graph;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin>>N;
    graph.resize(N+1);
    
    for(int i=0; i<N-1; i++){
        int a,b; cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    int q; cin>>q;
    for(int i=0; i<q; i++){
        int t,k; cin>>t>>k;
        if(t==1){
            if(graph[k].size()>1) cout<<"yes"<<'\n';
            else cout<<"no"<<'\n';
        }
        else cout<<"yes"<<'\n';
    }
}

 

풀이

문제 해결 아이디어는 생각보다 되게 간단합니다. 

먼저 단절선인 경우는 신경을 쓰지 않아도 됩니다. 

위 그림을 예시로 살펴봤을 때 어느 단절선을 자르더라도 전부 그래프가 2개 이상으로 나누어지기 때문입니다.

단절점인 경우에는 잘보면 리프 노드의 경우에는 나누더라도 2개 이상으로 분리가 되지 않는 것을 볼 수 있습니다. 따라서 이 문제는 리프 노드인지 아닌지를 찾는 문제라고 볼 수 있습니다.