[白俊]1707分チャート

問題の概要

グラフィック頂点の集合を2つの集合に分割し、各集合に属する頂点間を隣接しない集合に分割できる場合、これらのグラフィックを特に二分図(Bipartte Graph)と呼ぶ.
グラフィックが入力されると、そのグラフィックが二分グラフィックであるか否かを判別するプログラムを作成します.

アイデア

グラフィックをブラウズするときに、深度が偶数か奇数かをチェックします.
深度が偶数の頂点間、深度が奇数の頂点間を同じグループにマッピングできるためです.

注意事項

グラフィックのcomponentは1つではなく、複数でもよいので、アクセスしていない頂点を起点に再選択してbfsを行います.

ミス

アクセスされていない頂点を開始点(seed)として再抽出するプロセスは、1番から線形に行われます.
でもトップポイントが多すぎてコンディションになってないの?頂点もたくさんあります(自分だけがコンポーネントです).このような頂点に遭遇した場合,さらに1番からseed抽選を行うと,極端な場合(シグマi=1~n i)=O(n^2)の時間的複雑度が発生する.
BFSを行うにはO(N+E)のコストが必要であるが,問題は予想される範囲を超えている.

コードcpp

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

vector<int> g[20001];
int visited[20001];
void init_graph(int sz) {
	for (int i = 1; i <= sz; i++) {
		visited[i] = 0;
		g[i] = vector<int>();
	}
}
int get_pivot(int sz) {
	for (int i = 1; i <= sz; i++) {
		if (visited[i] == 0&&!g[i].empty()) {
			return i;
		}
	}
	return -1;
}

int check(int c,int m) {
	//child 체크
	if (visited[c] != 0) {
		if (visited[c] % 2 == m % 2) {
			return -1;
		}
		return 0;
	}
	return 1;
}

bool bfs(int s) {
	bool is_bip = true;
	queue<int> q;
	q.push(s);
	visited[s] = 1;

	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		//cout << cur <<" : "<< visited[cur] << endl;
		for (int i = 0; i < g[cur].size(); i++) {
			int child = g[cur][i];
			int child_valid = check(child, visited[cur]);
			//cout << child << "child valid : " << child_valid << endl;
			if (child_valid==1) {
				q.push(child);
				visited[child] = visited[cur] + 1;
			}
			if (child_valid == -1) {
				is_bip = false;
				break;
			}
		}
	}
	return is_bip;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin >> t;
	for (int ctr = 0; ctr < t; ctr++) {
		int v, e;
		cin >> v >> e;
		init_graph(v);
		for (int c2 = 0; c2 < e; c2++) {
			int a, b;
			cin >> a >> b;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		//cout << "done getting a graph" << endl;
		//문제점 : 컴포넌트가 하나가 아닐 수도 있다.

		bool is_bip = true;
		int seed;
		while ((seed = get_pivot(v)) != -1) {
			//cout <<"seed: "<< seed << endl;
			is_bip = bfs(seed);
			if (!is_bip) {
				break;
			}
		}
		cout << (is_bip ? "YES" : "NO") << endl;
	}
}