Aizu Online Judge 0086 Patrol

■0086 Patrol

いわゆる一筆書き．ただし，この問題では，スタート地点からゴール地点へ良く必要があるので，以下のように頂点A，Bを追加する．

A----S(Graph)G---B

あとは，以下の条件(「一筆書き - Wikipedia」からの引用)の内，2つ目の条件をみたすかを調べるだけ(字数が奇数である頂点とは，ここではAとBのこと)．

ある連結グラフが一筆書き可能な場合の必要十分条件は、以下の条件のいずれか一方が成り立つことである（オイラー路参照）。

• すべての頂点の次数（頂点につながっている辺の数）が偶数 → 運筆が起点に戻る場合（閉路）
• 次数が奇数である頂点の数が2で、残りの頂点の次数は全て偶数　→ 運筆が起点に戻らない場合（閉路でない路）

import java.util.*;
import java.util.Map.Entry;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 HashMap<Integer, Integer> map;

 void run(){
  map=new HashMap<Integer, Integer>();
  for(; sc.hasNext();){
   map.clear();
   for(;;){
    int v=sc.nextInt();
    int u=sc.nextInt();
    if((v|u)==0){
     break;
    }
    if(!map.containsKey(v)){
     map.put(v, 0);
    }
    if(!map.containsKey(u)){
     map.put(u, 0);
    }
    map.put(v, map.get(v)+1);
    map.put(u, map.get(u)+1);
   }
   map.put(1, map.get(1)+1);
   map.put(2, map.get(2)+1);
   boolean even=true;
   for(Entry<Integer, Integer> entry : map.entrySet()){
    even&=entry.getValue()%2==0;
   }
   println(even?"OK":"NG");
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}