728x90 반응형 이분 그래프1 [백준] 1707번 : 이분 그래프 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1. 문제 설명 2. 풀이과정 노드의 집합을 2개로 나누는데, 인접한 노드끼리 같은 집합이 되지 않도록 적절하게 임의로 분할할 수 있다고 한다. 트리의 경우에는 항상 이분 그래프가 된다는 것을 알 수 있는데, 사이클이 발생하지 않으면 탐색을 하면서 다음 노드를 이번 노드와 다른 집합으로 지정하면 되기 때문이다. 하지만 사이클이 발생했을 때 이분 그래프가 불가능할 수도 있다. 이런 경우에는 기존의 탐색 메커니즘에서 탐색한 노드에 다시 접근하게 되었을 때 현재 노드.. 2024. 2. 6. 이전 1 다음 728x90 반응형
