문제 링크 (opens new window)

풀이

1. 입력 범위가 애초에 N이 100,000이기 때문에 DFS나 BFS로 풀 생각은 하면 안됐다
2. 단절선이 생기면 반드시 그래프가 2개 이상으로 쪼개진다.
3. 간선이 하나밖에 없는 노드가 단절점이다.

import Foundation

let N = Int(readLine()!)!

var adj: [[Int]] = .init(repeating: [], count: N+1)
var edges: [(Int, Int)] = []

for _ in 0..<N-1 {
    let edge = readLine()!.split(separator: " ").map { Int($0)! }
    adj[edge[0]].append(edge[1])
    adj[edge[1]].append(edge[0])
    edges.append((edge[0], edge[1]))
}

let q = Int(readLine()!)!

for _ in 0..<q {
    let tk = readLine()!.split(separator: " ").map { Int($0)! }; let t = tk[0]; let k = tk[1]

    if t == 1 {
        // k 단절점 체크
        // dfs하다가 단절점
        if adj[k].count >= 2 {
            print("yes")
        } else {
            print("no")
        }
    } else if t == 2 {
        // k번쩌 간선이 단절선
        print("yes")
    }
}