BOJ 14675 - 단절점과 단절선 링크
(2023.06.16 기준 S1)

문제

정점이 N개인 트리가 주어진다. 그리고 t = 1일 땐 k번 정점이 단절점인지, t = 2일 땐 k번째 간선이 단절선인지에 대한 쿼리 t k가 q개 주어진다. 쿼리를 알맞게 처리.

알고리즘

단절점과 단절선이 트리에선..?

풀이

위 그림을 살펴보자.
빨강 정점이 단절점이다. 직관적으로 바로 알 수 있다.
단절점은 자식이 없는 리프 노드를 제외한 모든 점이다.
단, 예외가 있다. 바로 루트.
위 그림을 보면 루트는 자식이 존재함에도 불구하고 단절점이 되지 못한다. 다른 점을 루트로 잡으면, 현 루트는 결국 자식이 없는 리프 노드가 된다.
그래서 루트는 자식 수가 2 이상이어야 단절점이 될 수 있다.

단절선은? 위 두 그림에서 어떤 간선을 제거해도 둘 이상으로 나뉘게 된다. 결국 트리에서의 모든 간선은 단절선이다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;

bool is_cut[MAXN + 1];
vector<int> graph[MAXN + 1];

void dfs(int i, int p){
    int child = 0; // 자식 수
    for (auto j: graph[i]){
        if (j == p) continue; // 부모는 제외
        child++;
        dfs(j, i);
    }

    if (i == 1){ // 루트이면서 자식 수가 2 이상이면 단절점
        if (child >= 2) is_cut[i] = true;
    }
    else{ // 루트가 아니면서 자식이 있다면 단절점
        if (child) is_cut[i] = true;
    }
}

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

    int N; cin >> N;

    for (int i = 0, a, b; i < N - 1; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    fill(is_cut + 1, is_cut + N + 1, false);
    dfs(1, 0);

    int q, t, k; cin >> q;
    while (q--){
        cin >> t >> k;
        if (t == 1) // 정점에 대한 쿼리
            cout << (is_cut[k] ? "yes" : "no") << '\n';
        else // 모든 간선은 단절선
            cout << "yes" << '\n';
    }
}

• Python

import sys; input = sys.stdin.readline
sys.setrecursionlimit(100000)

def dfs(i, p):
    child = 0 # 자식 수
    for j in graph[i]:
        if j == p: # 부모는 제외
            continue
        child += 1
        dfs(j, i)

    if i == 1: # 루트이면서 자식 수가 2 이상이면 단절점
        if child >= 2:
            is_cut[i] = True
    else: # 루트가 아니면서 자식이 있다면 단절점
        if child:
            is_cut[i] = True

N = int(input())

graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

is_cut = [False] * (N + 1)
dfs(1, 0)

for _ in range(int(input())):
    t, k = map(int, input().split())
    if t == 1: # 정점에 대한 쿼리
        print('yes' if is_cut[k] else 'no')
    else: # 모든 간선은 단절선
        print('yes')