BOJ)1707 이분 그래프 (다시보기)

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

모든 edge의 양 끝에 vetex가 존재할 때, 각 vertex의 색깔이 다를 경우, 이분 그래프의 조건을 충족시킨다.

012345

#include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <cstring> //edge의 양 끝 vertex는 서로 다른 색깔을 가져야한다. using namespace std; int vertex_num, edge_num; vector<int> graph[20001]; int colored[20001];//0:none 1:blue 2:red void DFS(int position, int color) { colored[position] = color; for (int i = 0; i < graph[position].size(); i++) { int next_position = graph[position][i]; if (colored[next_position] == 0) { DFS(next_position, color == 1 ? 2 : 1); } } } int main() { int case_num; int vertex_left, vertex_right; cin >> case_num; while (case_num--) { cin >> vertex_num >> edge_num; while (edge_num--) { cin >> vertex_left >> vertex_right; graph[vertex_left].push_back(vertex_right); graph[vertex_right].push_back(vertex_left); } for (int i = 1; i <= vertex_num; i++) { //vertex에 색깔 칠하기 if (colored[i] == 0) { DFS(i, 1); } } bool res_check = true; for (int i = 1; i <= vertex_num; i++) { for (int j = 0; j < graph[i].size(); j++) { int next_position = graph[i][j]; if (colored[i] == colored[next_position]) res_check = false; //edge의 양 끝 vertex의 색깔이 같은지 다른지 확인 } } if (res_check) cout << "YES\n"; else cout << "NO\n"; //초기화 for (int i = 1; i <= vertex_num; i++) { graph[i].clear(); colored[i] = 0; } } }