[백준] 1707번: 이분 그래프

인접리스트로 그래프를 표현하고

dfs로 탐색했다.

이 그래프가 이분 그래프라는 가정하에 A쪽과 B쪽이 있으면

체크배열엔 아직 방문하지 않았으면 0,

A에 방문했으면 1,

B에 방문했으면 2를 표시했다.

방문하지않은 노드에 방문했다는 표시는 1또는 2이므로

dfs의 파라미터로 c값을 추가하여 재귀적으로 함수를 부를 때 3-c를 넘기도록 했다.

(처음에 c=1이면 다음번엔 c=3-c=2, 그 다음번엔 c=3-c=1 ...)

dfs가 끝나고나면 이 그래프가 이분그래프인지 확인하는 절차를 가지는데,

인접리스트로 표현되어있는 그래프이므로

이분그래프라면 해당 정점에 연결되어있는 정점들과는 다른 체크 값을 가져야한다.

만약 같은 값을 가졌다면 이분 그래프가 아니다!

그래프를 저장한 벡터배열과

체크배열을 초기화(clear)하는 것에 유의해야한다!

코드↓

1%