[백준 14675번] 단절점과 단절선 (C++)

문제링크 : https://www.acmicpc.net/problem/14675

14675번: 단절점과 단절선

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, Q;
vector<int>v[100001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    for(int i=0; i<N-1; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    cin >> Q;

    while(Q--)
    {
        int t, k;
        cin >> t >> k;

        if(t==1)
        {
            cout << (v[k].size()>=2 ? "yes" : "no") << "\n"; //끝점이 아니면 단절점
        }
        else
        {
            cout << "yes" << "\n"; //트리에서 모든 간선은 단절선
        }

    }

    return 0;
}

 

트리에서 현재 트리에 연결된 값이 2이상(현재 정점이 끝점이 아니라면) 단절점이다.

끝점의 경우 연결된 값이 1개이기에 그래프가 2개이상으로 나뉠수가 없다.

 

그리고 트리에서 모든 간선은 단절선이기에 바로 yes를 출력해주면 된다.