불꽃놀이의 아름다움 2

• 풀이는 에디토리얼 참고
• 그래프가 단순사이클을 한개만 갖고 있는 형태라는 것을 눈치채면, 답은 최대 3이라는 것을 알수 있으므로, 2-colorable 인지만 확인하면 된다. 시간복잡도는 O(V+E)이므로 O(N)이다.

"""Solution code for "BOJ 33915. 불꽃놀이의 아름다움 2".

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

Tags: [bi-coloring]
"""

import sys
from teflib import graph as tgraph


def main():
    N = int(sys.stdin.readline()) 
    graph = tgraph.create_graph_from_input(N, N)
    print('2' if tgraph.is_bipartite(graph) else '3')


if __name__ == '__main__':
    main()

• Dependency: teflib.graph.is_bipartite