백준 1707번 [이분 그래프](C++) -yes6686- 티스토리

백준 문제 풀이: 1707 [이분 그래프]

---

문제 링크: https://www.acmicpc.net/problem/1707

문제 설명:

주어진 그래프가 이분 그래프인지 판별하는 문제입니다. 이분 그래프란, 그래프의 정점을 두 그룹으로 나누었을 때, 같은 그룹 내의 정점들끼리는 간선이 존재하지 않는 그래프를 의미합니다.

주어진 그래프의 정점 수 (V)와 간선 수 (E) 및 각 간선 정보 (a, b)를 입력받아, 그래프가 이분 그래프이면 "YES", 아니면 "NO"를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<int> v[20001];
int visited[20001];
int check = 0;

void dfs(int a) {
    for (int i = 0; i < v[a].size(); i++) {
        int k = v[a][i];
        if (visited[k] == 1) {
            if (visited[a] == 1) {
                check = 1;
            }
        } else if (visited[k] == -1) {
            if (visited[a] == -1) {
                check = 1;
            }
        } else {
            if (visited[a] == 1) {
                visited[k] = -1;
            } else {
                visited[k] = 1;
            }
            dfs(k);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    while (T--) {
        int V, E;
        cin >> V >> E;
        for (int i = 0; i < E; i++) {
            int a, b;
            cin >> a >> b;
            v[a].push_back(b);
            v[b].push_back(a);
        }
        check = 0;

        for (int i = 1; i <= V; i++) {
            if (visited[i] == 0) {
                visited[i] = 1;
                dfs(i);
            }
        }

        if (check == 1) {
            cout << "NO" << '\n';
        } else {
            cout << "YES" << '\n';
        }

        memset(visited, 0, sizeof(visited));
        for (int i = 1; i <= V; i++) {
            v[i].clear();
        }
    }
}

예제

입력:
2
3 2
1 2
2 3
4 4
1 2
2 3
3 4
4 1

출력:
YES
YES

---

코드 설명

• DFS로 이분 그래프 탐색: DFS를 이용해 정점을 방문하며, 현재 정점과 연결된 정점에 서로 다른 값을 할당합니다.
• 이분 조건 확인: DFS 중 같은 그룹에 속한 정점이 연결된 경우 "NO"를 출력합니다.
• 초기화: 테스트 케이스마다 방문 배열 및 그래프 정보를 초기화합니다.

시간 복잡도

• DFS 탐색: O(V + E), V는 정점의 수, E는 간선의 수입니다.
• 전체 복잡도: 여러 테스트 케이스를 처리하므로, 총 복잡도는 O(T * (V + E))입니다.

---

결과

이 코드는 주어진 그래프가 이분 그래프인지 정확히 판별할 수 있습니다. 더 효율적인 접근 방법이나 추가 개선 사항은 언제든 환영합니다!