[백준/BOJ] 백준 1707번 : 이분 그래프

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

1707번: 이분 그래프

이분 그래프는 정점이 인접한 정점과 다른 집합이므로 각 정점에서 dfs를 하여 이분 그래프인지 확인한다. 이분 그래프 인지 확인하는 방법은 현재 정점이 check집합이라고 할 때, 인접한 정점은 check*(-1) 집합이라고 하고 인접한 정점으로 dfs 해가며 어떤 정점이 인접한 정점과 같은 집합이 되게 될 때 이분 그래프를 만들 수 없다고 하였다. 

 

코드

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int k, v, e;
vector<vector<int>> adj(20001);
int check_v[20001];
int visited[20001];

//here노드가 check(1또는-1)집합일때 이분 그래프가 가능한지 확인한다
bool Solve(int here, int check)
{
	bool ret = true;

	visited[here] = 1;
	check_v[here] = check; //check집합이라고 체크

	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i];

		//인접한 노드가 같은 집합으로 되어있으면 이분 그래프를 만들 수 없다
		if (visited[there] == 1 && check_v[there] == check)
			return false;

		//there에 방문한적이 없다면 방문한다. 이때 집합은 check*(-1) 이다 (here집합과 다른 집합)
		if (visited[there] == 0)
		{
			ret = Solve(there, check*(-1));

			//there탐색 결과 이분그래프를 만들 수 없다고 확인될때
			if (!ret)
				return ret;
		}
	}

	return ret;
}

void adjReset()
{
	for (int i = 0; i < 20001; i++)
		adj[i].clear();
}

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

	int temp1, temp2;
	bool result;

	cin >> k;

	for (int test = 0; test < k; test++)
	{
		adjReset();
		memset(visited, 0, sizeof(visited));
		memset(check_v, 0, sizeof(check_v));

		cin >> v >> e;
		for (int i = 0; i < e; i++)
		{
			cin >> temp1 >> temp2;
			adj[temp1].push_back(temp2);
			adj[temp2].push_back(temp1);
		}

		result = true;

		//각 정점들에서 시작하는 그래프중에 이분 그래프를 만들 수 없는게 있는지 확인한다
		for (int i = 1; i <= v; i++)
		{
			if (visited[i] == 0)
			{
				result = Solve(i, 1);

				//i정점에서 시작하는 그래프가 이분 그래프를 만들 수 없을때
				if (!result)
					break;
			}
		}

		if (result)
			cout << "YES" << "\n";
		else
			cout << "NO" << "\n";
	}



	return 0;
}