이분 그래프에 대해 잘못이해해서 틀린 문제이다. 이분 그래프(bipartite graph)란 그래프의 정점들을 두 개의 집합으로 나눌 수 있는 그래프를 의미한다.

좌측 그래프는 인접한 2와 4번 정점이 서로 같은 파란색을 보유하고 있기 때문에 이분 그래프가 아니고 우측 그래프는 서로 다른 색을 보유하고 있기 때문에 이분 그래프가 성립된다. 문제를 잘못 이해해 Union-find를 이용해 해결하고자 하였었다.

오답

#include <iostream>
#include <vector>
#define endl "\n"

using namespace std;

int k, v, e;
vector<int> graph;

int find_parent(int x) {
    if (graph[x] == x) {
        return x;
    } else {
        return graph[x] = find_parent(graph[x]);
    }
}

void union_(int a, int b) {
    int a_result = find_parent(a);
    int b_result = find_parent(b);
    if (a_result != b_result) {
        graph[a_result] = b_result;
    }
}

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

    cin >> k;
    for(int i = 0; i < k; i++) {
        cin >> v >> e;
        graph.clear();
        graph.resize(v + 1);

        // Initializing the graph
        for (int z = 1; z <= v; z++) {
            graph[z] = z;
        }

        for (int j = 0; j < e; j++) {
            int a, b;
            cin >> a >> b;
            union_(a, b);
        }

        // Example of checking if the graph is fully connected (not related to bipartiteness)
        bool is_connected = true;
        int parent = find_parent(1);
        for (int z = 2; z <= v; z++) {
            if (find_parent(z) != parent) {
                is_connected = false;
                break;
            }
        }

        if (is_connected) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

정답 출처

#include <iostream>
#include <vector>
#include <queue>
#define endl "\n"
#define red 1
#define blue 2

using namespace std;

int k, v, e;
vector<int> g[200001];
int color[200001] = { 0 };

void coloring(int start) {
	queue<int> q;
	q.push(start);
	int c = red;
	color[start] = c;
	while (!q.empty()) {
		int now = q.front();
		q.pop();

		if (color[now] == red) {
			c = blue;
		}
		else if (color[now] == blue) {
			c = red;
		}

		for (int i = 0; i < g[now].size(); i++) {
			if (!color[g[now][i]]) {
				color[g[now][i]] = c;
				q.push(g[now][i]);
			}
		}

	}
}

void check() {
	for (int i = 1; i <= v; i++) {
		for (int j = 0; j < g[i].size(); j++) {
			if (color[i] == color[g[i][j]]) {
				cout << "NO" << endl;
				return;
			}
		}
	}
	cout << "YES" << endl;
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> k;
	for (int i = 0; i < k; i++) {
		cin >> v >> e;
		for (int j = 1; j <= v; j++) {
			g[j].clear();
			color[j] = 0;
		}
		for (int j = 0; j < e; j++) {
			int a, b;
			cin >> a >> b;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		for (int j = 1; j <= v; j++) {
			if (!color[j]) {
				coloring(j);
			}
		}
		check();
	}
	

	return 0;
}