반응형

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
반응형

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

 

12893번: 적의 적

첫 줄에 용재 주위 사람의 수 N(1 ≤ N ≤ 2,000)과 적대관계의 수 M(0 ≤ M ≤ 1,000,000)이 주어진다. 두 번째 줄부터 M개의 줄에 거쳐 서로 적대관계에 있는 사람의 번호 A, B(1 ≤ A, B ≤ N)가 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. enemy 배열을 만들어 최초의 적을 저장해 줍니다.

 

4. Union-Find를 이용하여 각 노드의 적들을 연결해 줍니다.

 

5. 이때 서로 같은 그룹에 속해 있다면 이론은 틀린 것이므로 0을 출력하고, 그렇지 않다면 1을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
int vect[2001];
int enemy[2001];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        int A, B;
        scanf("%d %d", &A, &B);
 
        if (Find(A) == Find(B)) {
            printf("0");
            return 0;
        }
 
        if (enemy[A] == 0) {
            enemy[A] = B;
        }
        else {
            Union(Find(enemy[A]), B);
        }
 
        if (enemy[B] == 0) {
            enemy[B] = A;
        }
        else {
            Union(Find(enemy[B]), A);
        }
    }
 
    printf("1");
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17398번 - 통신망 분할 (C++)  (0) 2023.06.06
[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05
[ 백준 ] 15789번 - CTP 왕국은 한솔 왕국을 이길 수 있을까? (C++)  (0) 2023.06.03
[ 백준 ] 17022번 - Sleepy Cow Sorting (C++)  (0) 2023.06.02
[ 백준 ] 14595번 - 동방 프로젝트 (Large) (C++)  (0) 2023.06.01

+ Recent posts

티스토리툴바