문제 링크 https://www.acmicpc.net/problem/13344 문제 요약 수식이 주어졌을 때 주어진 수식들이 일관성이 있는지 혹은 모순이 있는지 찾아내는 문제다. 문제 풀이 수식은 크게 두가지 종류가 존재한다. 1. \(u = v\) : \(u\)와 \(v\)는 같다 2. \(u \gt v\) : \(u\)가 \(v\)보다 크다 만약 1번 수식이 없다고 생각을 해보자. 1번 수식이 없고 2번 수식만 있을 때 주어진 수식들이 일관성이 있는지 없는지 어떻게 판단을 할 수 있을까? \(u\)와 \(v\)가 나오고 \(\gt\)가 화살표 처럼 생겼으므로 \(u\)에서 \(v\)로 향하는 방향 그래프를 만들어 보자. 이 때 만약 \(Cycle\)이 있으면 어떻게 될까? \(Cycle\)이 존재하도..
disjoint set
문제 링크 https://www.acmicpc.net/problem/2843 문제 요약 \(N\)개의 정점가 \(N\)개의 간선을 가지는 방향그래프가 주어진다. 각각의 정점은 최대 한개의 나가는 간선을 가질 수 있다. 이 때 두 가지의 쿼리를 처리해야 한다. 첫 번재 쿼리는 \(x\)번 정점에서 나가는 간선을 지우는 것이도 두 번째 쿼리는 \(x\)번 정점에서 나가는 간선을 따라 계속해서 움직일 때 마지막으로 도착하는 정점이 어디인지, 만약 영원히 끝나지 않는다면 영원히 끝나지 않는다고 출력을 해야 한다. 문제 풀이 연결된 그래프에서 간선을 지워서 두개의 분리된 그래프로 만드는 작업은 생각보다 어려운 일이다. 하지만 반대로 두개의 분리된 그래프를 하나로 합쳐 새로운 그래프를 만드는 작업은 꽤 쉬운 일이다..
