BOJ - 1707 - 이분 그래프
문제
문제
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.
출력
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.
제한
- 2 ≤ K ≤ 5
- 1 ≤ V ≤ 20,000
- 1 ≤ E ≤ 200,000
예제 입력 1
1
2
3
4
5
6
7
8
9
10
2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2
예제 출력 1
1
2
3
YES
NO
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
using namespace std;
// 테케, 정점, 간선
int k, v, e;
int visited[20004];
// dfs
void dfs(int start, vector<int> v[])
{
// 방문하지 않았더라면 색 1 부여
if(!visited[start])
visited[start] = 1;
// 색 1을 부여한 접한 접점들 조사
for(int i=0; i < v[start].size(); i++)
{
int idx = v[start][i];
// 방문을 하지 않았더라면
if(!visited[idx])
{ // 이전 방문 요소가 1번 색이라면
if(visited[start] == 1)
visited[idx] = 2;
// 이전 방문 요소가 2번 색이라면
else if(visited[start] == 2)
visited[idx] = 1;
// 다음 요소 방문
dfs(idx, v);
}
}
}
string check(int V, vector<int> v[])
{
for(int j=1; j <= V; j++)
for(int a=0; a < v[j].size(); a++)
{
int idx = v[j][a];
if(visited[j] == visited[idx])
return "NO";
}
return "YES";
}
// 2분 그래프 ... 두 색으로 표현 하되
int main()
{
cin >> k;
for(int i=0; i < k; i++)
{
cin >> v >> e;
int V, E;
vector<int> v[200004];
// graph 생성
for(int j=0; j < e; j++)
{
cin >> V >> E;
v[V].push_back(E);
v[E].push_back(V);
}
for (int i = 1; i <= V; i++)
if (!visited[i])
dfs(i, v);
cout << check(V, v) << endl;
// 초기화
fill(visited, visited + 20004, 0);
}
return 0;
}
SOL
- 양 방향 그래프 생성
- dfs를 통해 visited 컬러 부여
- check 를 이용하여 전 후 간선이 같다면 NO 출력