•
접근 방법
처음에 작성했던 코드는 자신의 정점에서 연결되어있지 않은 모든 정점을 모두 이어서 계산했습니다. 그래프의 정점의 개수 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);
}
C++
복사
