백준 1707 이분 그래프

📘 이분 그래프 판별 (DFS 활용)

📌 문제 설명

• K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.
• 사이클이 발생하지 않으면 이분 그래프로 나눌 수 있다.

🔍 이분 그래프의 성질

• DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 이전 노드와 같은 집합이면 이분 그래프가 아님
• 연결된 두 노드가 서로 다른 그룹에 속해 있으면 이분 그래프 조건을 충족한다.
• 이분 그래프는 두 개의 집합으로 나눌 수 있는 그래프다.
• 그래프의 모든 간선이 A 그룹의 노드와 B 그룹의 노드를 연결한다.
• 같은 색의 노드들끼리는 서로 연결되지 않고, 항상 다른 색의 노드들끼리만 연결된다.

📝 예시

v1 -- v2 | | v4 -- v3

• 이 그래프도 이분 그래프이다.
• 네모 형태를 비틀어 보면,

v1 v3 \ / /\ \/ / \ v4 v2

• A그룹 노드 한쪽에 두고 B그룹 노드 저쪽에 두고 선을 쭉쭉 연결하면 전부 이분 그래프가 된다.
• 아래는 이분 그래프에 대한 그림이다.(출처 : 위키백과)
  
  

---

💡 입출력 예시

2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2
YES
NO

---

💻 코드

#include <bits/stdc++.h>  
using namespace std;  

vector<vector<int>> adj_list;  
vector<int> visited;  // 0: 미방문, 1: 그룹 A, 2: 그룹 B  
bool isBipartite;  

void DFS(int node, int group) {  // 스택 프레임마다 달라지는 변수는 파라미터로.  
    visited[node] = group;  // 현재 방문 처리  

    for (int next_node : adj_list[node]) {  // 인접 노드 순회  
        if (visited[next_node] == 0) {  // 미방문 노드라면  
            DFS(next_node, 3 - group);  // 방문 & 그룹 처리 (1 → 2, 2 → 1)  
        } else if (visited[next_node] == visited[node]) {  // 방문 & 같은 그룹  
            isBipartite = false;  
            return;  
        }  
    }  
}  

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

    int N;  
    cin >> N;  

    for (int i = 0; i < N; i++) {  
        int v, e;  
        cin >> v >> e;  
        adj_list.assign(v + 1, vector<int>());  
        visited.assign(v + 1, 0);  // 0으로 초기화  
        isBipartite = true;  

        for (int i = 0; i < e; i++) {  
            int s, e;  
            cin >> s >> e;  
            adj_list[s].push_back(e);  
            adj_list[e].push_back(s);  
        }  

        for (int i = 1; i <= v; i++) {  
            if (visited[i] == 0) {  
                DFS(i, 1);  // 그룹 1부터 시작  
            }  
            if (!isBipartite) break;  
        }  

        cout << (isBipartite ? "YES" : "NO") << "\n";  
    }  
}

출처

https://en.wikipedia.org/wiki/Bipartite_graph