読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

aoj 0086

グラフ Aizu Online Judge c++

パトロール | Aizu Online Judge
一筆書き可能か判定する問題, すなわちグラフGが与えられた時そのグラフがオイラー路であるか判定すればよい.
オイラー路となる条件は,

  1. すべての頂点の次数が偶数⇔オイラー閉路(オイラーグラフ)
  2. 奇数次数の頂点が2つで残りが偶数次数⇔準オイラーグラフ

でこれらの時のみに一筆書きが可能である.
なお今回のケースでは始点と終点が指定されているので, これらの次数が奇数で残りが偶数であるかどうかを判定すれば良い.

int main()
{
  int a[101]={};
  int x, y;
  while(cin>>x>>y)
  {
    if(!x&&!y)
    {
      int c=0;
      for(int i=3;i<101;i++)c+=(a[i]%2);
      printf("%s\n",(c==0&&a[1]%2==1&&a[2]%2==1)?"OK":"NG");
      fill_n(a,101,0);
    }
    else
    {
      a[x]++;
      a[y]++;
    }
  }
}