사용자 도구

사이트 도구


ps:problems:boj:7535

A Bug’s Life

ps
링크acmicpc.net/…
출처BOJ
문제 번호7535
문제명A Bug’s Life
레벨골드 2
분류

이분 그래프

시간복잡도O(T*(V+E))
인풋사이즈T<=?, V<=2000, E<=1000000
사용한 언어Python
제출기록103500KB / 1780ms
최고기록1660ms
해결날짜2022/11/07
태그

[라이]2-SAT 문제

풀이

  • 그래프가 이분 그래프인지 확인하면 되는 문제. 시간복잡도는 O(E+V)
  • 라이 블로그에서 2-SAT 연습문제로 이 문제가 주어지는 바람에, 처음에는 레벨이 높게 측정되었다가 시간이 지나면서 제자리를 찾아온것 같다

코드

"""Solution code for "BOJ 7535. A Bug’s Life".

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

Tags: [Bipartite Graph]
"""

import sys
from teflib import graph as tgraph


def main():
    scenario_count = int(sys.stdin.readline())
    for scenario_no in range(1, scenario_count + 1):
        bug_count, interaction_count = [
            int(x) for x in sys.stdin.readline().split()
        ]
        graph = [[] for _ in range(bug_count)]
        for _ in range(interaction_count):
            u, v = [int(x) for x in sys.stdin.readline().split()]
            graph[u - 1].append(v - 1)
            graph[v - 1].append(u - 1)

        print(f'Scenario #{scenario_no}:')
        if tgraph.is_bipartite(graph):
            print('No suspicious bugs found!')
        else:
            print('Suspicious bugs found!')
        print()


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
N​ M D N​ D
 
ps/problems/boj/7535.txt · 마지막으로 수정됨: 2022/11/07 15:41 저자 teferi