원수의 원수

• Friend-enemy coloring 문제에서 처리할 것이 조금 더 많아진 문제. 친구와 원수 뿐 아니라 추가적으로 Unknown이나 Error을 처리해야 한다.
• 적의 적에서 처럼 BFS를 이용해서 컬러링을 구하고, 이때 추가로 연결요소 번호까지 저장해 놓은 다음에, 두 노드가 연결되어 있는지 여부와 컬러가 같은지 여부를 함께 고려하면 답을 O(1)에 찾을수 있다. O(V+E+K)로 해결할 수 있다
• 그러나 이것저것 다 하려면 그냥 Disjoint Set을 사용하는게 더 간편하다. 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¹⁾.

"""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()

• Dependency: teflib.disjointset.DisjointSet