백준 1707 이분 그래프

1번 집합과 2번 집합으로 나눠서 생각하기 위해서, bfs, dfs에 필요한 visit 배열이나 check배열을 bool로 선언하는 것이 아니라 int 배열로 선언하여, 0은 방문하지 않은 것, 1은 1번 집합 2는 2번 집합으로 둔다.

 

문제에서 조건을 잘 봐야 한다. v<=20,000인데 전에 풀던 코드를 그대로 쓰다보니 런타임 에러가 계속 발생했다.

문제 조건을 놓치지 말자.

또한, vector.clear()함수를 통해서 초기화 해주는 작업을 놓치지 말자.

테스트 케이스가 여러 개가 되는 경우는 특히 조심하자.

 

자세한 설명은 아래 주석으로..

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
 
int n, m;
int color[1000000];
vector<int> g[20001];
 
bool dfs(int x, int c) {
    color[x] = c;
    
    for (int i = 0; i < g[x].size(); i++) {
        int next = g[x][i];
 
        if (color[next] == 0) {
            //현재 node가 1번 집합이면, 다음은 2번 집합이 될 것.
            //현재 node가 2번 집합이면, 다음은 1번 집합이 될 것.
            //bool값을 반환하므로, 재귀적으로 들어가서 false가 나오면 false를 반환해야 한다.
            if (dfs(next, 3 - c) == false) return false;
        }
        //방문한 적이 있을 때, 현재 node와 다음 들어갈 node의 색이 같으면 false
        else if (color[x] == color[next]) return false;
    }
 
    return true;
}
 
int main(int argc, char** argv) {
    int t;
    cin >> t;
 
    while (t--) {
        cin >> n >> m;
        //테스트 케이스가 여러 개니까 check 배열을 초기화 해준다.
        //그래프도 초기화 해준다.
        for (int i = 1; i <= n; i++) {
            //0은 방문하지 않은 것
            color[i] = 0;
            g[i].clear();
        }
 
        for (int i = 0; i < m; i++) {
            int from, to;
            cin >> from >> to;
            g[from].push_back(to);
            g[to].push_back(from);
        }
        //방문 안한곳이 없도록 다 돌려준다.
        bool ok = true;
        for (int i = 1; i <= n; i++) {
            //처음 방문하는 곳은 1번 집합으로 만든다.
            if (color[i] == 0) {
                if (dfs(i, 1) == false)ok = false;
            }
        }
        if (ok)printf("YES\n");
        else printf("NO\n");
    }
 
    return 0;
}