사용자 도구

사이트 도구


ps:problems:boj:12893

적의 적

ps
링크acmicpc.net/…
출처BOJ
문제 번호12893
문제명적의 적
레벨골드 4
분류

이분 그래프

시간복잡도O(V+E)
인풋사이즈V<=2,000, E<=1,000,000
사용한 언어Python
제출기록103492KB / 1484ms
최고기록1456ms
해결날짜2022/11/07

풀이

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

코드

코드 1 - BFS (teflib)

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

코드 2 - Disjoint set

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

토론

댓글을 입력하세요:
M O U V I
 
ps/problems/boj/12893.txt · 마지막으로 수정됨: 2022/11/12 02:40 저자 teferi