테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 원수의 원수 ======

===== 풀이 =====
  * [[ps:2색 색칠#Friend-enemy coloring]] 문제에서 처리할 것이 조금 더 많아진 문제. 친구와 원수 뿐 아니라 추가적으로 Unknown이나 Error을 처리해야 한다.
  * [[ps:problems:boj:12893]]에서 처럼 BFS를 이용해서 컬러링을 구하고, 이때 추가로 연결요소 번호까지 저장해 놓은 다음에, 두 노드가 연결되어 있는지 여부와 컬러가 같은지 여부를 함께 고려하면 답을 O(1)에 찾을수 있다. O(V+E+K)로 해결할 수 있다
  * 그러나 이것저것 다 하려면 그냥 [[ps:Disjoint Set]]을 사용하는게 더 간편하다. [[ps:2색 색칠#Friend-enemy coloring]] 에서 설명한것처럼 A,B가 친구면 A,B를 합치고 ~A,~B를 합친다. A,B가 원수이면 ~A,B를 합치고 A,~B를 합친다. 이제 x,y 쿼리에 대해서, x가 y, ~y와 모두 같은 그룹이면 Error, y랑만 같은 그룹이면 친구, ~y랑만 같은 그룹이면 원수, 둘다 같은 그룹이 아니면 unknown이다. 이경우의 시간복잡도는 O((E+K)*α(V)).

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 23818. 원수의 원수".

- Problem link: https://www.acmicpc.net/problem/23818
- Solution link: http://www.teferi.net/ps/problems/boj/23818
"""

import sys
from teflib import disjointset


def main():
    N, M, K = [int(x) for x in sys.stdin.readline().split()]
    dsu = disjointset.DisjointSet(N * 2)
    for _ in range(M):
        t, a, b = [int(x) for x in sys.stdin.readline().split()]
        if t == 0:
            dsu.union(a - 1, b - 1)
            dsu.union(a - 1 + N, b - 1 + N)
        else:
            dsu.union(a - 1, b - 1 + N)
            dsu.union(a - 1 + N, b - 1)
    for _ in range(K):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        a_set = dsu.find(a - 1)
        if a_set == dsu.find(b - 1):
            print('Error' if a_set == dsu.find(b - 1 + N) else 'Friend')
        else:
            print('Enemy' if a_set == dsu.find(b - 1 + N) else 'Unknown')


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:disjointset#DisjointSet|teflib.disjointset.DisjointSet]]

{{tag>BOJ ps:problems:boj:골드_3}}