[BOJ알고리즘, C++]#14675_단절점과 단절선, 트리, 단절점, 단절선

#1. 문제

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

 

---

 

#2. 풀이

 

1. 트리

[자료구조]#5_트리

트리 자료구조는 그래프의 한 종류로, 1:N 관계의 계층 구조를 갖는 비 선형 자료구조입니다. 트리 자료구조는 비 순환 구조로, 두 노드 사이의 경로는 유일합니다.  

 

2. 단절점

트리 자료구조에서 차수가 2 이상인 정점이 단절점입니다. 트리 자료구조는 비 순환 구조로 어느 두 정점을 연결하는 경로는 유일하기 때문에, A - B - C 경로에서 B정점을 제거할 경우, 두 그래프로 나누어집니다. 따라서, 차수가 2 이상인 B와 같은 정점은 항상 단절점이 됩니다. 

 

3. 단절선

트리 자료구조의 모든 간선은 단절선입니다. 트리 자료구조는 비 순환 구주로 어느 두 정점을 연결하는 경로는 유일하기 때문에, 경로를 구성하는 모든 간선은 단절선이 됩니다.

 

4. 진입 차수 계산!

1. 먼저, 2차원 vector 컨테이너를 활용하여 그래프를 구성합니다. 이때, 각 정점의 진입 차수를 계산합니다.
2. 질의를 입력 받고, 1일 경우 해당 정점의 진입 차수가 2 이상일 경우 "yes" 아니면, "no"를 출력합니다.
3. 질의를 입력 받고, 2일 경우 무조건 "yes"를 출력합니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/14675
*   @문제: 단절점, 단절선 여부를 출력하는 문제
*   @설명
        0. 트리는 계층 구조를 갖는 비순환 구조의 그래프
        
        1. 단절점? 차수가 2이상인 정점은 단절점이다.
        - 비순환 구조이기 때문에 어느 두 정점을 연결하는 경로는 유일하기 때문입니다.
        - 따라서, A - B - C 에서 B를 제거할 경우 A - C를 연결하는 경로가 사라져 두 그래프로 나뉘어집니다.
        - 반대로, 그래프 자료구조일 경우 A - B - C에서 B를 제거해도 A - D - C의 가능성도 존재하기 때문에
        - 진입 차수가 2이상인 B가 무조건 단절점이라고 단언할 수 없습니다. 
        2. 단절선? 모든 간선이 단절선이다.
        - 비순환 구조이기 때문에 모든 간선은 연결하는 두 정점의 유일한 경로입니다.
        - 따라서, A - B에서 간선을 제거하면 A와 B를 연결하는 유일한 경로가 사라지기 때문에 모든 간선은 단절선입니다.
        - 반대로, 그래프 자료구조일 경우 A - B의 간선을 제거해도 A - C - B로 연결되는 경로가 존재할 수 있기 때문에
        - 모든 간선이 단절선이라고 단언할 수 없습니다.
*/


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

using namespace std;

#define MAX 100001

int N, q, t, k;
int degree[MAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    //@진입 차수
    vector<vector<int>> tree(N+1);
    for(int i=0; i<N-1; ++i)
    {
        int u, v;
        cin >> u >> v;

        degree[u]++;
        degree[v]++;
    }

    //@질의
    cin >> q;
    while(q--)
    {
        cin >> t >> k;
        //@단절점
        if(t==1)
        {
            if(degree[t] >= 2) cout << "yes";
            else cout << "no";
        }
        else if(t==2)
        {
            cout << "yes";
        }
        cout << '\n';
    }

    return 0;
}

 

---