二部グラフ判定

問題

実行時間制限: - / メモリ制限: -
頂点数 \(n\) の無向グラフが与えられる。隣接している頂点同士が違う色になるように、頂点に色を塗っていく。\(2\) 色以上ですべての頂点を塗ることができるか判定せよ。多重辺やループはないものとする。

入力

  • 頂点数 \(n\) が与えられる。続く \(n\) 行で各頂点 \(u\) の隣接リストが以下の形式で与えられる。
\(u \hspace{8px} k \hspace{8px} v_1 \hspace{8px} v_2 \hspace{8px} ... \hspace{8px} v_k\)

\(u\) は頂点の番号、\(k\) は \(u\) の出次数、 \(v_1 v_2 ... v_k\) は \(u\) に隣接する頂点の番号を示す。

出力

  • \(2\) 色以上ですべての頂点を塗ることができる場合は \(Yes\) を、できない場合は \(No\) を出力せよ。

制約

  • \(1 \leqq n \leqq 1000\)

例1

入力

\(3\)
\(0 \hspace{8px} 2 \hspace{8px} 1 \hspace{8px} 2\)
\(1 \hspace{8px} 2 \hspace{8px} 0 \hspace{8px} 2\)
\(2 \hspace{8px} 2 \hspace{8px} 0 \hspace{8px} 1\)

出力

\(No\)

例2

入力

\(4\)
\(0 \hspace{8px} 2 \hspace{8px} 1 \hspace{8px} 3\)
\(1 \hspace{8px} 2 \hspace{8px} 2 \hspace{8px} 3\)
\(2 \hspace{8px} 2 \hspace{8px} 1 \hspace{8px} 3\)
\(3 \hspace{8px} 2 \hspace{8px} 0 \hspace{8px} 2\)

出力

\(Yes\)

【出典】
秋葉拓哉 , 岩田陽一他「プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~」93〜94頁

解答例(C++)

#include <bits/stdc++.h>
using namespace std;

int n;
int graph[1000][1000];
int color[1000];

bool dfs(int i, int c) {
  color[i] = c;
  for (int j = 0; j < n; j++) {
    if (graph[i][j] == 0) {
      continue;
    }
    if (color[j] == c) {
      return false;
    }
    if (color[j] == 0) {
      dfs(j, 0 - c);
    }
  }
  return true;
}

int main() {

  cin >> n;

  // 各変数を初期化
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      graph[i][j] = 0;
    }
    color[i] = 0;
  }

  // 入力を受け取る
  for (int i = 0; i < n; i++) {
    int u, k;
    cin >> u >> k;
    for (int j = 0; j < k; j++) {
      int v;
      cin >> v;
      graph[u][v] = 1;
    }
  }

  // 探索する
  for (int i = 0; i < n; i++) {
    if (color[i] == 0) {
      if (!dfs(i, 1)) {
        cout << "No" << endl;
        return 0;
      }
    }
  }

  // 探索で詰まらなかったらYes
  cout << "Yes" << endl;

  return 0;
}