백준 이분 그래프

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

dfs문제인데 한 3일 넘게 걸려서 오늘 스프링 공부를 못햇네요 ㅠ 

일단 중요한 키포인트는  아래 코드인데 

if (colors[glists[k][i] - 1]==0) {
		  if (dfs(glists[k][i], 3 - cnt) == false) {
				return false;
		  }
}else if(colors[glists[k][i] - 1]==cnt){
			return false;
}

colors가 0이면 아직 색이 없는 상태

colors가 1이면 1번칼라 

colors가 2이면 2번 칼라로 지정 됩니다.

여기서 현재 칼라가 잇는 상태에서 색칠할 칼라가 동일한 경우 그래프는 이분 그래프가 될수가 없습니다.

colors[glists[k][i] - 1]==cnt

즉 예를들어 아래와 같은 노드가 연결이 되있다고 가정하겠습니다.

1 2
3 4
3 5
4 5

그리고 colors의 번호가 들어가는 값인 1을 R, 2를 B 칼라라고 가정하겠습니다.

인접노드로 만들면 아래와 같은 리스트가 만들어집니다.

1 - 2
2 - 1
3 - 4 - 5
4 - 3- 5
5 - 3 -4

시작은 1번노드에서 1은 R칼라가 됩니다. colors[0]=1; cnt=1

그리고 다음 노드가 2번으로 이동시 2번은 B 칼라가 됩니다. colors[1]=2; cnt=2 

그다음 2번 노드로 이동시 끊어진 노드이기에 

 

2번노드로 다시 시작합니다. colors[1]은 1이기 때문에 if (colors[i-1] == 0) 아니기 때문에 dfs에서 패스가 됩니다.

 

그러면 다음인 3번노드로 시작합니다. 

 3은 B 칼라가 됩니다. 칼라는 colors[2]=1;가 됩니다.cnt=1

다음은 4번 노드로 가서 칼라는 colors[3]=2이 됩니다. cnt=2 

다음은 3번 노드로 다시 가기 때문에  colors[2]=1이고  cnt는 1이므로 서로 다르므로 true로 return합니다.

그래서 return하고 조건인 false가 아니기 때문에 다시 return합니다. 돌아기 때문에 5번 노드로 갑니다.

 

그러면 맨처음 3은 칼라 B 상태에서 5번을 노드로 갑니다. 5번 노드는 colors[4]=2가 됩니다. cnt=2;

5번 노드의 3번과 4번을 체크합니다. 그러면 이때 colors[3]번이 cnt=2와 동일하기 때문에 return false가 되어 

이분그래프가 아니게 됩니다.  

 

정답:

#include <iostream>
#include <vector>
#include <queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<map>
#include<stack>
using namespace std;

struct Point {
	int i, j;
	int cnt = 0;
	
};

void Prints(vector<vector<int>>maps, int n, int m) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << maps[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

void Prints(vector<vector<bool>>maps, int n, int m) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << maps[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<vector<char>>maps, int n, int m) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<vector<vector<char>>>maps, int n, int m, int k) {
	for (int t = 0; t < k; t++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << maps[t][i][j];
			}
			cout << endl;
		}
		cout << endl;
	}
	cout << endl;
}

void Prints(vector<vector<vector<bool>>>maps, int n, int m, int k) {
	for (int t = 0; t < k; t++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << maps[t][i][j];
			}
			cout << endl;
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<int>line, int n) {
	for (int i = 0; i < n; i++) {
		cout << line[i] << ",";
	}
	cout << endl;
}
void Prints(string str, int n) {
	for (int i = 0; i < n; i++) {
		cout << str[i] << ",";
	}
	cout << endl;
}

bool checkmaps(vector<vector<int>>maps, vector<vector<int>>anw, int n, int m) {
	bool bCheck = false;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (maps[i][j] != anw[i][j]) {
				bCheck = true;
				i = n + 1;
				j = m + 1;
				continue;
			}
		}

	}
	return bCheck;

}
bool findstart(vector<vector<int>>maps, vector<vector<int>>anw, int n, int m, int) {
	bool bCheck = false;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (maps[i][j] != anw[i][j]) {
				bCheck = true;
				i = n + 1;
				j = m + 1;
				continue;
			}
		}

	}
	return bCheck;

}
bool checkmaps(vector<vector<bool>>maps, int n, int m) {
	//bool bCheck = false;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (maps[i][j] == false) {
				//bCheck = true;
				return true;
			}
		}
	}
	return false;
}
struct Data {
	Point p;
	int cnt;
	int sum;
};
vector<vector<int>>glists;
vector<bool>gbChecks;
vector<int>colors;
int gv, ge;
bool bConfirm = false;
bool dfs( int k ,int cnt) {

	gbChecks[k - 1] = true;
	colors[k - 1] = cnt;
	for (int i = 0; i < glists[k].size(); i++) {
		if (colors[glists[k][i] - 1]==0) {
		  if (dfs(glists[k][i], 3 - cnt) == false) {
				return false;
		  }
		}
		else if(colors[glists[k][i] - 1]==cnt){
			return false;
		}
	}
	return true; 
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//그래프
	//정점 집합을 둘로 분열
	//각 집합에 속한 정점끼리는 인접하지 않도록 분할 할수 잇을때
	//그러한 그래프를 특별히 이분 그래프 라고 한다.
	int k;
	cin >> k;
	
	//각 정점은 1부터 v까지 차례로 번호가 붙어 잇다.
	//e개의 줄에 걸쳐 간선에 대한 정보가 주어지는데 
	vector<string>anw;
	for (int t = 0; t < k; t++)
	{
		bConfirm = false;
		//v 정점,e간선의 갯수
		int v, e;
		cin >> v >> e;
		gv = v;
		ge = e;
		vector<vector<int>>lists(v+1);
		vector<bool>bChecks(v,false);
		gbChecks=bChecks;
		colors.clear();
		for (int i = 0; i < v; i++) {
			colors.push_back(0);
		}

		for (int i = 0; i < e; i++) {
			int x, y;
			cin >> x >> y;
			
			if (x > y) {
				int tmp = x;
				x = y;
				y = tmp;
			}

			lists[x].push_back(y);
			lists[y].push_back(x);

		}
		glists = lists;
		for (int i = 1; i < v + 1; i++) {
			if (colors[i-1] == 0) {
				bool bTEST = dfs(i, 1);
				if (bTEST == false) {
					bConfirm = true;
					break;
				}
			}
		}

		if (bConfirm == true) {
			anw.push_back("NO");
		}
		else {
			anw.push_back("YES");
		}
	}
	for (int i = 0; i < anw.size(); i++)
	{
		cout << anw[i] << endl;
	}
}