1707번: 이분 그래프

• 접근 방법

처음에 작성했던 코드는 자신의 정점에서 연결되어있지 않은 모든 정점을 모두 이어서 계산했습니다. 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)를 생각해보면, V+E의 시간복잡도를 이용해야 시간 내에 문제를 풀 수 있지만, 저 방법으로 한다면 최악의 경우 V^2이 되므로 400,000,000의 연산이 필요해서 시간초과가 나오게 됩니다. 이분 그래프의 개념을 알고 있지 않던 저는 어떻게 해야 이 문제를 풀 수 있을지 고민을 했는데, 문득 Red-Black Tree가 생각이 났습니다. 결국에는 자신과 인접한 노드들은 모두 자신과 다른 값을 가지고 있어야 하고, 그 다음 노드들도 모두 마찬가지이고 만약 이미 특정 값을 가지고 있다면 그 반대 값 즉 1 또는 2로 표현할 수 있고 값이 없는 것은 0으로 두어서 자신의 인접 노드 중에서 0이 아닌 자신과 같은 값이 있다면 그것은 이분 그래프로 표현이 가능하지 않다고 생각하고 문제를 풀었습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#define endl "\\n"

size_t K, V, E;
std::vector<std::vector<int> >adj_list;
std::vector<int> check;
std::vector<int> visited;
int ans;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> K;
}

void solve_input()
{
	int a, b;

	std::cin >> V >> E;
	adj_list = std::vector<std::vector<int> >(V + 1);
	check = std::vector<int>(V + 1, 0);
	visited = std::vector<int>(V + 1, 0);
	ans = 1;
	for (size_t i = 0 ; i < E ; i++)
	{
		std::cin >> a >> b;
		adj_list[a].push_back(b);
		adj_list[b].push_back(a);
	}
}

void dfs(int vertex, int val)
{
	if (visited[vertex])
		return ;
	visited[vertex] = 1;
	for (size_t i = 0 ; i < adj_list[vertex].size(); i++)
	{
		if (check[adj_list[vertex][i]] != 0 && (val == check[adj_list[vertex][i]]))
		{
			ans = 0;
			return;
		}
		if (check[adj_list[vertex][i]] == 0)
		{
			if (val == 1)
				check[adj_list[vertex][i]] = 2;
			else if (val == 2)
				check[adj_list[vertex][i]] = 1;
		}
	}
	for (size_t i = 0; i < adj_list[vertex].size(); i++)
	{
		if (val == 1)
			dfs(adj_list[vertex][i], 2);
		else
			dfs(adj_list[vertex][i], 1);
	}
}

void print_val()
{
	if (ans)
		std::cout << "YES" << endl;
	else
		std::cout << "NO" << endl;
}

void solve()
{
	solve_input();
	for (size_t i = 1 ; i <= V ; i++)
	{
		dfs(i, 1);
	}
	print_val();
}

int main()
{
	input();
	while(K--)
		solve();
	return (0);
}