AOJ0086 Patrol

問題リンク Patrol

• 解法

道を一筆書きできるかを判定する問題です。
頂点の次数を調べていき、次数が奇数の頂点が0もしくは2個ならば一筆書き可能です。
0個の場合にオイラーグラフと呼び、2個の場合に準オイラーグラフと呼びます。
前者は閉路を持ち、後者は閉路を持ちません。
この問題では開始点と終点が異なるので、準オイラーグラフでないとだめです。
つまり、開始点と終点の次数のみが共に奇数であるかどうかを調べればおｋです。

• ソース

import java.util.Scanner;

//Patrol
public class AOJ0086 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int[] a = new int[101];
			while(true){
				int s = sc.nextInt();
				int t = sc.nextInt();
				if((s|t)==0)break;
				a[s]++;
				a[t]++;
			}
			int o = 0;
			for(int s:a)if(s%2==1)o++;
			System.out.println(o!=2?"NG":a[1]%2==1&&a[2]%2==1?"OK":"NG");
		}
	}
}