質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
87.20%
グラフ理論

グラフ理論とは、頂点(node)と辺(edge)で構成されたグラフに関する数学理論で、グラフの多様な性質を探求することを指します。グラフは、頂点と向き(矢印)を持つ辺で構成された有向グラフと、矢印のない無向グラフに分類。さまざまな日常の場面で使用することを目的としている理論です。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

解決済

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

kay_ventris4
kay_ventris4

総合スコア263

グラフ理論

グラフ理論とは、頂点(node)と辺(edge)で構成されたグラフに関する数学理論で、グラフの多様な性質を探求することを指します。グラフは、頂点と向き(矢印)を持つ辺で構成された有向グラフと、矢印のない無向グラフに分類。さまざまな日常の場面で使用することを目的としている理論です。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

1回答

0評価

0クリップ

287閲覧

投稿2022/07/23 08:32

問題

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

方針

グラフ全体が連結である時:ノード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(); }

質問

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

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

まだ回答がついていません

会員登録して回答してみよう

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

グラフ理論

グラフ理論とは、頂点(node)と辺(edge)で構成されたグラフに関する数学理論で、グラフの多様な性質を探求することを指します。グラフは、頂点と向き(矢印)を持つ辺で構成された有向グラフと、矢印のない無向グラフに分類。さまざまな日常の場面で使用することを目的としている理論です。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。