적의 적

• 적대 관계 노드쌍 사이에 에지를 연결했을때 2색 색칠이 가능하면 이론이 성립한다. 7585와도 거의 같은 문제.
• 그래프가 2색 색칠이 가능한지, 다시말해 이분그래프인지 확인하는 것은 BFS나 DFS를 사용해서 간단히 처리할수 있고 이 경우의 시간복잡도는 O(V+E)이다. 또는 Disjoint Set을 사용해서 이분 그래프 여부를 확인하는 방법도 있긴 하다. 이 경우의 시간복잡도는 O(E*α(V))로 복잡도 상에서는 별 차이 없지만, 실제 실행속도는 두배정도 느렸다. (BFS는 1468ms, disjoint set은 2504ms)

"""Solution code for "BOJ 12893. 적의 적".

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

Tags: [Bipartite graph]
"""

import sys
from teflib import graph as tgraph


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    graph = [[] for _ in range(N)]
    for _ in range(M):
        A, B = [int(x) for x in sys.stdin.readline().split()]
        graph[A - 1].append(B - 1)
        graph[B - 1].append(A - 1)

    try:
        tgraph.two_coloring(graph)
    except ValueError:
        print('0')
    else:
        print('1')


if __name__ == '__main__':
    main()

• Dependency: teflib.graph.two_coloring

"""Solution code for "BOJ 12893. 적의 적".

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

Tags: [Bipartite graph]
"""


import sys
from teflib import disjointset


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    dsu = disjointset.DisjointSet(N * 2)
    for _ in range(M):
        A, B = [int(x) for x in sys.stdin.readline().split()]

        if dsu.find(A - 1) == dsu.find(B - 1):
            print('0')
            break
        dsu.union(A - 1, B - 1 + N)
        dsu.union(B - 1, A - 1 + N)
    else:
        print('1')


if __name__ == '__main__':
    main()

• Dependency: teflib.disjointset.DisjointSet