有向グラフのオイラー路・オイラー閉路判定関数

ライブラリ 
#include <atcoder/dsu>
using namespace atcoder; // 忘れがち

// （有向グラフ版）
// オイラー路ライブラリ
// そもそも連結されているか (by BFS)
// 有向グラフなら始点に注意
// （どこを開始点にするかで全て訪れれるかが変わる）
// => UFで判定するように変更
bool is_connected(VV& G){
  ll N = G.size();
  dsu uf(N);
  rep(i,N){
    for(ll to : G[i]){
      uf.merge(i,to);
    }
  }
  if(uf.groups().size()==1)return true;
  return false;
}
// ※有向
// オイラー閉路が作れるか？
// 条件：すべての頂点について入次数＝出次数
bool is_eular_circuit(VV& G){
  ll N = G.size();
  VI in(N);
  VI out(N);
  rep(i,N){
    for(ll j : G[i]){
      // i to j
      out[i]++;
      in[j]++;
    }
  }
  rep(i,N){
    if(in[i]!=out[i])return false;
  }
  return true;
}
// ※有向
// オイラー路が作れるか？
// 条件：
// ある１点について、入次数＋１＝出次数
// ある１点について、入次数＝出次数＋１
// その他の点について、入次数＝出次数
bool is_eular_trail(VV& G){
  ll N = G.size();
  VI in(N);
  VI out(N);
  rep(i,N){
    for(ll j : G[i]){
      // i to j
      out[i]++;
      in[j]++;
    }
  }
  ll more_in=0;
  ll more_out=0;
  ll even=0;
  rep(i,N){
    if(in[i]==out[i]){
      even++;
    }
    // 1の差であることに注意(2以上の差があったら不可能)
    else if(in[i]==out[i]+1){
      more_in++;
    }
    else if(in[i]+1==out[i]){
      more_out++;
    }
    else{
      // 2以上の差
      return false;
    }
  }
  if(more_in==1 && more_out==1)return true;
  return false;
}

条件確認