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

問題

グラフが二部グラフか判定する問題

方針

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

コード

C++

#include <bits/stdc++.h>#include <math.h>using namespace std;#define ll long long /* infinity */ll inf = 1000000000000000000; /* judge by yes or no */void judge(bool x) { if (x) { cout << "Yes" << endl; } else { cout << "No" << endl; }} /* UnionFind */ /* unite(x, y), akin(x, y), root(x), size(x) */class UnionFind { public: vector <ll> par; vector <ll> siz; UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) { for (ll i = 0; i < sz_; ++i) par[i] = i; } void init(ll sz_) { par.resize(sz_); siz.assign(sz_, 1LL); for (ll i = 0; i < sz_; ++i) par[i] = i; } ll root(ll x) { while (par[x] != x) { x = par[x] = par[par[x]]; } return x; } bool unite(ll x, ll y) { x = root(x); y = root(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; return true; } bool akin(ll x, ll y) { return root(x) == root(y); } ll size(ll x) { return siz[root(x)]; }}; void solve() { ll N, M; cin >> N >> M; vector<vector<ll>> sample = {}; set<ll> heads = {}; vector<ll> rep = {}; UnionFind uf(N); vector<vector<ll>> graph = {}; for (ll i = 0; i < N; i++) { graph.push_back({}); } for (ll i = 0; i < M; i++) { ll a, b; cin >> a >> b; a--; b--; graph.at(a).push_back(b); graph.at(b).push_back(a); sample.push_back({a, b}); uf.unite(a, b); } for (ll i = 0; i < N; i++) { heads.insert(uf.root(i)); } for (ll el: heads) { rep.push_back(el); } if (rep.size() > 1) { for (ll i = 1; i < rep.size(); i++) { graph.at(0).push_back(rep.at(i)); graph.at(rep.at(i)).push_back(0); } } bool flag = true; vector<ll> dist = {}; for (ll i = 0; i < N; i++) { dist.push_back(inf); } dist.at(0) = 0; vector<bool> seen = {}; for (ll i = 0; i < N; i++) { seen.push_back(false); } seen.at(0) = true; deque<ll> data = {0}; while (data.size() > 0) { ll pos = data.at(0); data.pop_front(); for (ll el: graph.at(pos)) { if (seen.at(el) == true) { continue; } seen.at(el) = true; if (dist.at(el) == inf) { dist.at(el) = dist.at(pos) + 1; } data.push_back(el); } } for (vector<ll> el: sample) { if (dist.at(el.at(0)) % 2 == dist.at(el.at(1)) % 2) { flag = false; } } judge(flag);} int main() { solve();}

質問

以上のコードでごく一部のテストケースで不正解が出ます。どこのアルゴリズムまたはコード中の不備が原因でこうなってしまうのでしょうか？素人質問にて恐縮ですが、お力添えいただける箇所がございましたら、ご指摘のほど何卒よろしくお願い申し上げます。