二部グラフ判定 / 一部の不正解が取れない

問題

方針

グラフ全体が連結である時：ノード0から見た最短距離を調べる。あらかじめ保管しておいた各a_iとb_iについて、両者の0からの最短距離の偶奇が同じであるようなことがあれば二部グラフでなく、そのようなことが一度もなければ二部グラフと判定。
グラフ全体が連結でない時：UnionFind木を用いて各グラフの代表ノードを記録しておく。それらを全てノード0に繋ぎ、一つの連結なグラフとしてしまう。残りは上と同様の手法で判定。

コード

C++
1#include <bits/stdc++.h>
2#include <math.h>
3using namespace std;
4#define ll long long
5
6/* infinity */
7ll inf = 1000000000000000000;
8
9/* judge by yes or no */
10void judge(bool x) {
11	if (x) {
12		cout << "Yes" << endl;
13	}
14	else {
15		cout << "No" << endl;
16	}
17}
18
19/* UnionFind */ /* unite(x, y), akin(x, y), root(x), size(x) */
20class UnionFind {
21	public:
22	vector <ll> par;
23	vector <ll> siz;
24	UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) { for (ll i = 0; i < sz_; ++i) par[i] = i; }
25	void init(ll sz_) { par.resize(sz_); siz.assign(sz_, 1LL); for (ll i = 0; i < sz_; ++i) par[i] = i; }
26	ll root(ll x) {
27		while (par[x] != x) {
28			x = par[x] = par[par[x]];
29		}
30		return x;
31	}
32	bool unite(ll x, ll y) {
33		x = root(x); y = root(y);
34		if (x == y) return false;
35		if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; return true;
36	}
37	bool akin(ll x, ll y) {
38		return root(x) == root(y);
39	}
40	ll size(ll x) {
41		return siz[root(x)];
42	}
43};
44
45void solve() {
46	ll N, M; cin >> N >> M;
47
48	vector<vector<ll>> sample = {};
49	set<ll> heads = {};
50	vector<ll> rep = {};
51
52	UnionFind uf(N);
53 
54	vector<vector<ll>> graph = {};
55	for (ll i = 0; i < N; i++) {
56		graph.push_back({});
57	}
58	for (ll i = 0; i < M; i++) {
59		ll a, b; cin >> a >> b;
60		a--; b--;
61		graph.at(a).push_back(b);
62		graph.at(b).push_back(a);
63		sample.push_back({a, b});
64		uf.unite(a, b);
65	}
66	for (ll i = 0; i < N; i++) {
67		heads.insert(uf.root(i));
68	}
69
70	for (ll el: heads) {
71		rep.push_back(el);
72	}
73
74	if (rep.size() > 1) {
75		for (ll i = 1; i < rep.size(); i++) {
76			graph.at(0).push_back(rep.at(i));
77			graph.at(rep.at(i)).push_back(0);
78		}
79	}
80
81	bool flag = true;
82	vector<ll> dist = {};
83	for (ll i = 0; i < N; i++) {
84		dist.push_back(inf);
85	}
86	dist.at(0) = 0;
87	vector<bool> seen = {};
88	for (ll i = 0; i < N; i++) {
89		seen.push_back(false);
90	}
91	seen.at(0) = true;
92
93    deque<ll> data = {0};
94	while (data.size() > 0) {
95		ll pos = data.at(0);
96		data.pop_front();
97		for (ll el: graph.at(pos)) {
98			if (seen.at(el) == true) {
99				continue;
100			}
101			seen.at(el) = true;
102			if (dist.at(el) == inf) {
103				dist.at(el) = dist.at(pos) + 1;
104			}
105			data.push_back(el);
106		}
107	}
108
109	for (vector<ll> el: sample) {
110		if (dist.at(el.at(0)) % 2 == dist.at(el.at(1)) % 2) {
111			flag = false;
112		}
113	}
114
115	judge(flag);
116}
117
118int main() {
119    solve();
120}