A Bug’s Life

• 그래프가 이분 그래프인지 확인하면 되는 문제. 시간복잡도는 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()

• Dependency: teflib.graph.is_bipartite