Tags

2 pages

도달성

[Algorithm] cpp 백준 24272번: 루트 노드가 많은 트리일수록 좋은 트리이다

유일 경로 트리의 간선 방향을 제어하며 ‘모든 정점에 도달 가능한 루트’의 수를 유지하는 문제입니다. Euler tour로 서브트리를 구간화하고, child→parent 제약의 교집합과 parent→child 제약의 합집합을 각각 multiset과 세그먼트 트리로 관리하여 매 쿼리 O(log N)에 정답을 계산합니다. 엣지 케이스(교집합 공집합, 전역 인터벌, 무방향 전환)까지 안정적으로 처리합니다.
[Algorithm] cpp 백준 24272번: 루트 노드가 많은 트리일수록 좋은 트리이다

[Algorithm] cpp 백준 3311번: Traffic - SCC 압축과 DAG 구간 전파

섬 내부 도로망은 선분 도로가 교차하지 않는 평면 그래프이므로, SCC 압축 DAG에서 각 컴포넌트가 도달할 수 있는 동쪽 경계 정점 집합은 y좌표 기준 연속 구간이 됩니다. 이를 이용해 동쪽 경계 정점(서쪽에서 실제로 도달 가능한 것만)을 y 오름차순으로 인덱싱하고, 자식 구간을 부모로 병합하는 역위상 전파로 각 서쪽 정점의 답(서쪽 정점에서 도달 가능한 동쪽 정점 수)을 O(n+m)에 계산합니다. 구현은 반복형 Kosaraju + 압축 그래프 위상정렬 기반입니다.
[Algorithm] cpp 백준 3311번: Traffic - SCC 압축과 DAG 구간 전파