提出 #22050182

---

ソースコード 拡げる

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

using ll = long long;
using ld  = long double;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
const int INF=1e9+7;
const ll LINF=9223372036854775807;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld EPS = 1e-10; //微調整用（EPSより小さいと0と判定など）

int ii() { int x; if (scanf("%d", &x)==1) return x; else return 0; }
long long il() { long long x; if (scanf("%lld", &x)==1) return x; else return 0; }
string is() { string x; cin >> x; return x; }
char ic() { char x; cin >> x; return x; }
void oi(int x) { printf("%d ", x); }
void ol(long long x) { printf("%lld ", x); }
void od_nosp(double x) { printf("%.15f", x); } // 古い問題用
void od(double x) { printf("%.15f ", x); }
void os(const string &s) { printf("%s ", s.c_str()); }
void oc(const char &c) { printf("%c ", c); }
#define o_map(v){cerr << #v << endl; for(const auto& xxx: v){cout << xxx.first << " " << xxx.second << "ddddddddd\n";}} //動作未確認
void br() { putchar('\n'); }

// #define gcd __gcd //llは受け取らない C++17~のgcdと違うので注意
// int lcm(int a, int b){return a / gcd(a, b) * b;}
#define b_e(a) a.begin(),a.end() //sort(b_e(vec));
#define REP(i,m,n) for(ll i=(ll)(m) ; i < (ll)(n) ; i++ )
#define DREP(i,m,n) for(ll i=(ll)(m) ; i > (ll)(n) ; i-- )
#define rep(i,n) REP(i,0,n)
#define m_p(a,b) make_pair(a,b)
#define p_b push_back
#define SZ(x) ((ll)(x).size()) //size()がunsignedなのでエラー避けに
#define endk '\n'


// coutによるpairの出力（空白区切り）
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << " " << p.second << ")";}
// coutによるvectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << " "; //"\t"に変えるとTabで見やすく区切る
  }
  return s;
}
// coutによる多次元vectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i] << endl;
  }
  return s;
}

//最大値、最小値の更新。更新したor等しければtrueを返す
template<typename T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<typename T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}

//4近傍（上下左右） rep(i, 2) にすると右・下だけに進む
vector<int> dx_4 = {1, 0, -1, 0};
vector<int> dy_4 = {0, 1, 0, -1};

// -------- template end - //


// - library ------------- //

// #include <atcoder/all>
#include <atcoder/all>
using namespace atcoder;

// 10^18まではいけるようだが、10^19でオーバーフローする
// MODをつけたい場合もこれでもいい
// 繰り返し二乗法を使っているので O(logN) で計算できる
ll llpow(ll x, ll n){
  ll ans = 1;
  while (n > 0){
    if (n % 2 == 1) ans = ans * x; // % MOD; (MODつけたい場合のコピー用)
    x = x * x; // % MOD; (MODつけたい場合のコピー用)
    n /= 2; // n を右に1つビットシフト
  }
  return ans;
}


using Graph = vector<vector<ll>>;
bool is_bipartite_graph(const Graph &graph, vector<ll> &colors, int v, int c, ll &cnt) {
  if (colors[v] != -1) return true; // 無色じゃなければ無視

  // 無色なら、そこを塗って次へ行く
  cnt++;
  colors[v] = c;
  for (int u: graph[v]) {
    if (colors[u] == c) {
      return false;
    }
    if (colors[u] == -1 && !is_bipartite_graph(graph, colors, u, (c+1)%2, cnt)) {
      return false;
    }
  }
  return true;
}


// --------- library end - //




int main(){

  ll N, M;
  cin >> N >> M;

  vector<pll> edges(M); // 赤同士が隣接しないかの判定のため
  Graph adjs(N); // 隣接リスト表現
  vector<bool> seen(N, false);

  // adjs の作成
  rep(i, M){
    ll a, b;
    cin >> a >> b;
    a--; b--; // 0-indexed
    adjs[a].p_b(b);
    adjs[b].p_b(a); // undirected

    edges[i] = pll(a, b); // 赤同士が隣接しないかの判定のため
  }

  // 赤色で決め打つ箇所を bit 全探索 -> 決め打たなかった頂点を二部グラフ判定
  // 二部グラフであれば、緑・青で塗り分けられる
  // 塗り分け方の通り数は 2^(赤以外の頂点をグラフとしたときの連結成分数)
  
  // N個の要素 {0, 1, ..., n-1} の部分集合の全探索
  // colors[i] := -1:無色, 2:赤, 0:緑, 1:青
  ll ans = 0;
  for (ll bit = 0; bit < (1LL<<N); ++bit){
    vector<ll> colors(N, -1);
    rep(i, N){
      if (bit & (1LL<<i)){  // i番目のbitがtrue -> 赤で塗る
        colors[i] = 2;
      }
    }

    // 赤の頂点が隣接しているとNGなので、隣接頂点が赤同士でないか判定
    bool ng = false;
    for (pll p : edges){
      if (colors[p.first] == 2 && colors[p.second] == 2){
        ng = true;
        break;
      }
    }
    if (ng) continue;

    // 二部グラフ判定
    // なお、無色頂点が見つかった回数を cnt とする。cnt>0であれば二部グラフ判定の起点となった頂点なので、連結成分数を+1する
    ll cc_cnt = 0;
    bool is_bipartite = true;
    rep(i, N){
      ll cnt = 0;
      if (!is_bipartite_graph(adjs, colors, i, 0, cnt)){
        is_bipartite = false;
        break;
      }
      if (cnt > 0) cc_cnt++;
    }
    if (is_bipartite) ans += llpow(2, cc_cnt);
  }

  cout << ans << endk;

}

提出情報

ジャッジ結果