![]()
문제 풀이 분리 집합을 이용한다. 각 점이 하나의 노드이며, 입력이 간선이다. 간선을 들어오는 순서대로 사이클이 생기는 지 검사하면서 Union연산으로 노드를 잇는다. 코드 #include #include using namespace std; typedef struct { int x; int y; }edge; int parent[500'000]; int getParent(int n) { if (parent[n] == n) { return n; } return getParent(parent[n]); } bool cycle(int x, int y) { int p1 = getParent(x); int p2 = getParent(y); return p1 == p2; } void Union(int x, int y..
![]()
문제 풀이 `Union-Find` 알고리즘을 사용한다. 파티에 참가한 사람 별로 부모노드를 설정하여 서로간의 부모노드를 비교하여 같은 집합에 속해있는지 확인한다. 진실을 아는 집합 내의 사람이 파티에 속해있는 파티에서는 거짓말을 할 수 없다. 코드 #include #include using namespace std; vector knowns; vector parties[51]; int parent[51]; // 노드의 부모 노드를 반환 int getParent(int n) { if (parent[n] == n) { return n; } return getParent(parent[n]); } // 노드의 부모를 서로 연결하여 같은 집합에 속하게 한다. void Union(int n1, int n2) { n..
