algospot 에디터 전쟁 (문제 ID: EDITORWARS) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/EDITORWARS

algospot.com :: EDITORWARS

n개의 노드에 관한 m개의 관계가 주어진다.

만약 ack a b 라고 하면 a, b 가 같은 집합에 속해야 하고 만약 dis a b 라고 하면 a, b 가 서로 다른 집합에 속해야 한다.

이때 어떤 집합에 속할 수 있는 노드의 최대 갯수를 구하는 문제이다.

 

상호배타적집합을 사용하면 문제를 풀 수 있다.

한가지 주의할 점은 enemy라는 vector를 이용하여 적대관계(서로 다른 집하에 속해야만 하는)에 있는 집합의 루트 정보를 유지해야한다.

동지의 적은 적이므로 ack일때 merge할 상대와 적대관계에 있는 집합끼리 merge를 해야한다.

적의 적은 동지이므로 dis일때 dis인 상대의 적과 merge를 해야한다. 

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/25.%20disjointSet/EDITORWARS.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2