로그우 P1983 역급수 결정 (위상 정렬 활용)
문제 링크
https://www.luogu.org/problemnew/show/P1983
문제 설명
단방향 철도 노선 위에 1부터 n까지 번호가 매겨진 역이 있다. 각 역은 최소 1등급 이상의 등급을 가진다. 여러 대의 기차가 이 노선을 운행하며, 각 기차는 다음과 같은 조건을 만족한다: 만약 기차가 역 x를 정류한다면, 출발지와 도착지 사이에 등급이 역 x 이상인 모든 역은 반드시 정류해야 한다. ...
6월 18일 16:56에 게시됨
그래프 알고리즘의 응용: 연결성 관리와 조상 찾기
최근 두 가지 그래프 관련 문제를 접하게 되었는데, 각각 복잡한 구조를 다루는 데 있어 유사한 접근 방식을 사용하고 있어 정리해보았다.
AcWing 2069. 네트워크 분석
태그: 병합-찾기 집합, 동적 연결성 관리
이 문제는 초기에 간선이 없는 (n)개의 노드로 구성된 네트워크에서 시작한다. 두 가지 유형의 연산이 주어진다:
두 노드 (a)와 (b)를 연결한다.
노드 (p)에 값 ...
5월 23일 02:50에 게시됨