이분 그래프

개념

이분 그래프 예시

• 정의: 만약 정점의 집합 V와 E가 존재하고, 인접한 정점이 u와 v가 존재한다면 u  ∈ V 이면 v ∈E이다. 
• 결국은 위의 그림처럼 서로 인접한 정점들을 서로 다른 색으로 칠할 수 있다면 이분 그래프를 만족한다고 할 수 있다.

이분 그래프 문제

이미지 클릭

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int t;
bool f(vector<int> v1[], int x) {
  vector<int> v(x + 4, -1);
  queue<int> q;
  for (int i = 1; i <= x; i++) {
    if (v[i] == -1) {
      v[i] = 0;
      q.push(i);
      while (!q.empty()) {
        int xx = q.front();
        q.pop();
        for (int j : v1[xx]) {
          if (v[j] == -1) {
            v[j] = 1 - v[xx];
            q.push(j);
          } 
          else if (v[j] == v[xx]) return 0;
        }
      }
    }
  }
  return 1;
}
int main() {
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector<int> v[n + 4];
    for (int i = 0; i < m; i++) {
      int x, y;
      cin >> x >> y;
      v[x].push_back(y);
      v[y].push_back(x);
    }
    if (f(v, n)) cout << "YES\n";
    else cout << "NO\n";
  }
}

 

• 함수 부분만 확인해주면 되는데, 제일 먼저 모든 정점을 -1로 초기화시켜 주어 아직 방문하지 않음을 명시해 준다.

vector<int> v(x + 4, -1);

 

• 그런 다음 모든 정점을 돌아 주면서 아직 방문이 되지 않은 부분을 탐색해 준다.

for (int i = 1; i <= x; i++) 
    if (v[i] == -1)

 

• 기본적으로 정점을 0으로 만들어 주고, 차례 대로 연결된 정점을 1 - (정점의 숫자)의 방식으로 색을 칠해준다.
• 만약 연결된 정점의 숫자가 서로 같다면 바로 return 0를 해주면 된다.

v[i] = 0;
q.push(i);
while (!q.empty()) {
  int xx = q.front();
  q.pop();
  for (int j : v1[xx]) {
    if (v[j] == -1) {
    v[j] = 1 - v[xx]; //1-v[xx]를 해준다면 1 또는 0으로 정점을 색칠 해줄 수 있음!
    q.push(j);
    } 
    else(v[j] == v[xx]) return 0;//연결된 정점 중에서 색이 동일하다면 무조건 false!
    }
 }

이미지 클릭