백준 20040 사이클 게임 혼내주기
이 문제는 작년 PS를 시작하기 전 ICPC 예선에서 0솔을 하면서 봤던 문제 중 하나다. 그땐 보자마자 brute force로 다 확인하는 알고리즘으로 짜서 틀렸고, 어떻게 푸는지 감도 못잡았다. 다시 보니 유니온 파인드를 이용하는 것만 발견하면 간단한 문제다. #include using namespace std; int parent[500000]; int find(int u){ if(u == parent[u]) return u; return parent[u] = find(parent[u]); } bool merge(int u, int v){ u = find(u); v = find(v); if(u == v) return true; parent[u] = v; return false; } int main(..
혼내주기
2021. 8. 1. 23:01