백준 1707번 이분 그래프(C++)

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 20001

using namespace std;

int V, E;
int x, y;
int check = 0;

vector<int> vertex[MAX];

bool visited[MAX] = { false, };
int vertexCol[MAX] = { 0, };

void setgraph() {
	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		cin >> x >> y;
		vertex[x].push_back(y);
		vertex[y].push_back(x);
	}
}

void DFS(int here) {
	if (visited[here] == true)
		return;

	visited[here] = true;

	for (int i = 0; i < vertex[here].size(); i++) {
		int next = vertex[here][i];
		if (visited[next] == false) {
			if (vertexCol[here] == 1)
				vertexCol[next] = -1;
			else
				vertexCol[next] = 1;
			
		}
		if (vertexCol[here] == vertexCol[next]) {
			check = 1;
			return;
		}
		else
			DFS(next);
	}
}

void init_Col() {
	for (int i = 0; i <= V; i++) {
		vertexCol[i] = 0;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N;

	cin >> N;

	for (int i = 0; i < N; i++) {
		setgraph();

		for (int i = 1; i <= V; i++) {
			if (visited[i] == false) {
				vertexCol[i] = 1;
				DFS(i);
				init_Col();
			}
			if (check == 1)
				break;
		}

		if (check == 1)
			cout << "NO" << '\n';
		else
			cout << "YES" << '\n';

		for (int i = 1; i <= V; i++) {
			vertex[i].clear();
			visited[i] = false;
		}

		check = 0;
	}
}

하.. 엄청난 오답을 자랑했다. 

틀렸습니다는 내가 이분그래프가 뭔지 정확히 모르는 것이 문제였다. 난 이분 그래프가 1대1 함수같은 것이라 생각했다. 그래서 사이클을 형성하면 이분그래프가 아닐것이라 생각했다. 그러나 이분그래프는 그게 아니었다.

결론부터 말하면 이 문제는 사이클과 전혀 관련이 없다.

 

사이클이 무려 2개지만 이것은 이분 그래프이다.

 위 그래프를 보면 빨간색 점의 인접 정점은 모두 파란색이고 파란색 정점의 인접 정점은 모두 빨간색이다. 즉 이 그래프는 이분그래프이다. 때문에 시작점을 빨간색/파란색으로 결정해두고 DFS하며 빨간색과 파란색을 번갈아가며 지정해주고 각 계속해서 인접한 노드의 색깔을 확인해주면된다. 인접 정점 중 같은 색이 있다면 이분 그래프가 아닌 것이다.

 

난 왜 시간 초과가 났는가? 

 

이건 바보같이

방문 정점이 아니면 DFS한다는 것 까진 좋았는데 init() 함수에서 visited를 초기화해주고 있기 때문에 어차피 V번 DFS로 시간을 갖다 버리고 있었던 것이다. 이분 그래프 개념을 알고서 정답 출력은 금방 했는데 이걸 못찾아서 삽질하다가 무려 거의 1시간을 낭비했다... 다들 절대 안틀렸을거라 생각한 부분부터 살펴보길 ㅠ ㅠ