백준[BOJ] 1707번 : 이분그래프 - BFS, DFS

1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net BFS, DFS를 연습하기 좋은 문제라는 생각이 든다.

처음에 이분 그래프의 개념을 아예 몰라서, 이진트리를 의미하는 줄 알고 한참 고생했다.... 그림으로 보면 이해가 빠르다.

아래와 같다. 인접한 정점을 다른 색으로 모두 칠할 수 있으면 이분 그래프이다.

이분 그래프의 특징 인접한 정점들을 다른 색을 구분할 수 있다. 순환할 수 있다.(2가지 색으로 구분 가능하면 된다.)

최대 이분 매칭 문제(Maximum Bipartite Matching Pr.....