(1707) 이분 그래프

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

단계별로 풀어보기

27단계(그래프와 순회) 16번째

 

 

 

이분 그래프인지 확인하는 방법은 다음과 같다.

1) BFS나 DFS로 탐색하며 방문한 정점을 임의의 색으로 칠한다.

2) 다음 정점을 방문하며 현재 정점과 다른 색으로 칠한다.

3) 만약 다음 정점이 이미 칠해져 있고 현재 정점과 색이 같다면 이분 그래프가 아니다.

4) 모든 정점을 방문해 그러한 경우가 없다면 이분 그래프다.

 

 

 

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

bool solve(){
  int v, e;
  
  cin >> v >> e;
  
  vector adj(v+1, vector<int> ());
  vector check(v+1, -1);
  bool isBG= true;
  
  while(e--){
    int a, b;
    
    cin >> a >> b;
    
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  
  auto dfs= [&](auto self, int now, int state) -> void {
    check[now]= state;
    
    for(int next:adj[now]){
      if(check[next]==state)  isBG= false;
      if(check[next]!= -1)  continue;
      
      self(self, next, 1-state);
    }
  };
  
  for(int i=1;i<=v;i++){
    if(check[i]!=-1)  continue;
    
    dfs(dfs, i, 0);
  }
  
  return isBG;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    cout << (solve() ? "YES\n" : "NO\n");
  }
  
  return 0;
}