Aizu Online Judge 0086 Patrol

■0086 Patrol

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

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

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

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

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

view plainprint?

1. import java.util.*;  
2. import java.util.Map.Entry;  
3. import java.lang.*;  
4. import java.math.*;  
5. import java.io.*;  
6.   
7. import static java.lang.Math.*;  
8. import static java.util.Arrays.*;  
9.   
10. public class Main{  
11.   
12.  Scanner sc=new Scanner(System.in);  
13.   
14.  int INF=1<<28;  
15.  double EPS=1e-9;  
16.   
17.  HashMap<Integer, Integer> map;  
18.   
19.  void run(){  
20.   map=new HashMap<Integer, Integer>();  
21.   for(; sc.hasNext();){  
22.    map.clear();  
23.    for(;;){  
24.     int v=sc.nextInt();  
25.     int u=sc.nextInt();  
26.     if((v|u)==0){  
27.      break;  
28.     }  
29.     if(!map.containsKey(v)){  
30.      map.put(v, 0);  
31.     }  
32.     if(!map.containsKey(u)){  
33.      map.put(u, 0);  
34.     }  
35.     map.put(v, map.get(v)+1);  
36.     map.put(u, map.get(u)+1);  
37.    }  
38.    map.put(1, map.get(1)+1);  
39.    map.put(2, map.get(2)+1);  
40.    boolean even=true;  
41.    for(Entry<Integer, Integer> entry : map.entrySet()){  
42.     even&=entry.getValue()%2==0;  
43.    }  
44.    println(even?"OK":"NG");  
45.   }  
46.  }  
47.   
48.  void debug(Object... os){  
49.   System.err.println(Arrays.deepToString(os));  
50.  }  
51.   
52.  void print(String s){  
53.   System.out.print(s);  
54.  }  
55.   
56.  void println(String s){  
57.   System.out.println(s);  
58.  }  
59.   
60.  public static void main(String[] args){  
61.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
62.   new Main().run();  
63.  }  
64. }  

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();
 }
}