이분 그래프 판별하기

Step1: Problem Analysis
-‘A’,’B’,’C’의 상태가 하나의 노드이며 물을 붓는 동작이 간선.
-조건 중요! 한 물통이 비거나 다른 한 물통이 가득 찰 때까지
-입력:Test case 개수, Test case에 해당되는 Node 개수, Edge 개수가 입력됨.
-출력: 그래프의 이분 그래프 출력
Solution
-DFS 탐색
노드 둘이 인접하다는 뜻은 다른 집합이 돼야 한다는 뜻 그래프는 항상 이분 그래프. 사이클 발생시에만 같은 집합에 들어가 이분 그래프가 되지 않는 문제를 가진다는 것을 알 수 있음.
-답 구하기
DFS 알고리즘을 사용해 이미 방문한 노드가 나와 같은 집합이면 이분 그래프가 아님

Step2: Solve Manually

Step3: Pseudo Code

Step4: Implement Code “https://gist.github.com/growingpenguin/163671f66d95af5d85bda67dc0741bad”