반응형

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

 

1707번: 이분 그래프

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited 배열을 만들어 인접한 노드끼리 같은 집합에 속해있는지 체크합니다.

 

2. dfs를 통해 모든 노드를 탐색하며 인접한 노드끼리 같은 집합에 속해있다면 false를 return 합니다.

 

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int K, V, E;
vector<int> list[20001];
int visited[20001];
 
bool dfs(int cur, int stat)
{
    for (auto& next : list[cur]) {
        if (visited[next] == 0) {
            visited[next] = -stat;
            dfs(next, -stat);
        }
        else if (visited[next] == stat) {
            return false;
        }
    }
 
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> K;
 
    while (K--) {
        cin >> V >> E;
        bool flag = true;
 
        for (int i = 1; i <= V; i++) {
            list[i].clear();
            visited[i] = 0;
        }
 
        for (int i = 0; i < E; i++) {
            int u, v;
            cin >> u >> v;
            list[u].push_back(v);
            list[v].push_back(u);
        }
 
        for (int i = 1; i <= V; i++) {
            if (visited[i] == 0) visited[i] = 1;
            if (!dfs(i, visited[i])) {
                printf("NO\n");
                flag = false;
                break;
            }
        }
 
        if (flag) {
            printf("YES\n");
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1863번 - 스카이라인 쉬운거 (C++)  (0) 2023.06.29
[ 백준 ] 12869번 - 뮤탈리스크 (C++)  (0) 2023.06.28
[ 백준 ] 1963번 - 소수 경로 (C++)  (0) 2023.06.26
[ 백준 ] 5052번 - 전화번호 목록 (C++)  (0) 2023.06.25
[ 백준 ] 3649번 - 로봇 프로젝트 (C++)  (0) 2023.06.23

+ Recent posts

티스토리툴바