ps:problems:boj:13265
색칠하기
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 13265 |
| 문제명 | 색칠하기 |
| 레벨 | 골드 5 |
| 분류 |
이분그래프 |
| 시간복잡도 | O(T*(V+E)) |
| 인풋사이즈 | T<=?, V<=1000, E<=100000 |
| 사용한 언어 | Python 3.13 |
| 제출기록 | 38196KB / 376ms |
| 최고기록 | 284ms |
| 해결날짜 | 2026/03/05 |
풀이
- 기본적인 이분 그래프 (Bipartite graph) 판별 문제. 2색으로 색칠이 가능한 그래프 == 이분 그래프이다
- 시간복잡도는 O(V+E)
코드
"""Solution code for "BOJ 13265. 색칠하기".
- Problem link: https://www.acmicpc.net/problem/13265
- Solution link: http://www.teferi.net/ps/problems/boj/13265
Tags: [graph]
"""
from teflib import psutils
from teflib import graph as tgraph
@psutils.run_n_times
def main():
_n, _m, graph = tgraph.from_input()
print('possible' if tgraph.is_bipartite(graph) else 'impossible')
if __name__ == '__main__':
main()- Dependency: teflib.graph.is_bipartite
ps/problems/boj/13265.txt · 마지막으로 수정됨: 2026/03/26 09:50 저자 teferi
토론