Go Gradually - Repository

[USACO Gold] DAG - 위상 정렬

위상 정렬이란, Directed Acyclic Graph(DAG)의 정점들을 각 정점이 자신의 자식 정점들보다 먼저 방문되도록 나열하는 것을 의미한다.방향 그래프(directed graph)는 간선을 한쪽 방향으로만 이동할 수 있는 그래프를 의미한다.또한 비순환 그래프(acyclic graph)는 순환(cycle)을 포함하지 않는 그래프를 의미한다.이는 하나 이상의 간선을 따라가서 출발한 정점으로 다시 돌아올 수 없는 구조를 말한다.이 두 정의를 합치면, 방향 비순환 그래프(directed acyclic graph, 줄여서 DAG)는 간선을 한쪽 방향으로만 이동할 수 있고 순환을 포함하지 않는 그래프이다.위상 정렬 (Topological Sort) - Course Schedule다음 문제를 풀어보자. C..

[USACO Gold] Disjoint Set, 분리 집합, Union-find

그래프에 간선을 추가하고 그래프의 두 정점이 연결되어 있는지 검사할 수 있게 해 주는 자료구조가 분리 집합(DSU, Union-Find) 이다.USACO.guide는 알고리즘의 원리와 정의보단 어떻게 이 정의를 떠올릴 수 있는지에 집중한다.알고리즘의 원리와 정의가 중요하지 않다는 뜻이 아니다.실제 Union-find의 원리와 관련된 내용은 다음 링크를 참고 바란다. CS Academy csacademy.com 구현(Implementation)import java.util.*;public class DisjointSets { int[] parents; int[] sizes; public DisjointSets(int size) { parents = new int[size]; ..