BipartiteGraph_DFS

문제 복기

1. DFS의 기본 골격

static void dfs(int x) {
		if(c[x]) {return;}
		c[x] = true;
		System.out.print(x+" ");
		for(int y:g[x]) {
			if(c[y]==false) {
				dfs(y);
			}
		}
	}

이분 그래프 판별법

1. 인접 노드 별로 다른 번호를 부여한다. 1->2->1->2->..

2. n개의 노드에 대해 인접 노드 리스트 중에서 같은 그룹 번호가 있으면 이분 그래프가 아니다! A-B 1-2 C-B(B-C) 1-2(2-1) D-E 1-2 F-G 1-2

틀린 이유

1. main에서 dfs 호출할 때 0번 노드에 대해서만 dfs를 해버렸다. =>v개의 모든 노드와 그 인접 노드에 대해 dfs를 해주어야한다!

2. v개의 노드에 대해 dfs를 해줄 때 그냥 해주는 것이 아니라 중복체크해주어야한다! 그래프만 주구장창 풀때는 당연히 해주었던 것을 왜 까먹었나..

dfs(0,1);

for(int i=0;i<v;i++) {
	if(g[i]==0) {//방문체크해주고!
			dfs(i,1);
	}
}