백준 1707 C++

dfs한 번 돌려서 색을 칠하고 그래프 돌면서 옆이랑 같은 색인지 확인하면 끝이다.

#include <iostream>
#include <vector>

using namespace std;

int v, e;
vector<vector<int>> Graph;
vector<int> isvisited;

void input() {


	cin >> v >> e;

	Graph.assign(v + 1, vector<int>(0, 0));
	isvisited.assign(v + 1, 0);

	for (int i = 0; i < e; i++) {
		int cv, ce;

		cin >> cv >> ce;

		Graph[cv].push_back(ce);
		Graph[ce].push_back(cv);
	
	}
	
}

void dfs(int cur) {
	
	if (!isvisited[cur])
		isvisited[cur] = 1;

	for (int i = 0; i < Graph[cur].size(); i++) {
		
		int next = Graph[cur][i];

		if (!isvisited[next]) {
			if (isvisited[cur] == 1)
				isvisited[next] = 2;
			else if(isvisited[cur] == 2)
				isvisited[next] = 1;

			dfs(next);
		}
	}

}

bool isBiparie() {
	for (int i = 1; i <= v; i++) {
		for (int k = 0; k < Graph[i].size(); k++) {
			int next = Graph[i][k];

			if (isvisited[i] == isvisited[next])
				return false;
		}
	}

	return true;
}

int main() {

	int k; //k테스트 케이스, v vertex, e edge
	cin >> k;

	for (int i = 0; i < k; i++) {
		
		input();
		
		for (int k = 1; k <= v; k++) {
			if (!isvisited[k]) {
				dfs(k);
			}
		
		}
		if (isBiparie())
			cout << "YES\n";
		else
			cout << "NO\n";
	}

	
	

	return 0;
}