SPOJ 0442 "Searching the Graph" TDBFS

問題：http://www.spoj.pl/problems/TDBFS/

なぜか苦労したので試行の記録をしてみる．

問題自体は典型的な探索問題．
頂点の数nと，それぞれの頂点において隣接した頂点のリストが与えられる．
その入力でできるグラフから，指定された頂点と探索方法で通る頂点を列挙せよ．

DFSとBFSだから普通の実装をしてみる．
Javaだと何となく再帰が書きづらいのでそれぞれスタックとキューを使えばいいか．
頂点数も1000ぐらいだったら隣接行列でいいかな．
普通に数値を読み込んで行列につっこむ．
スタックとキューはそれぞれjava.util.Stackとjava.util.LinkedListでいいか．
最初のコード

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		for (int T = s.nextInt(), t = 0; t++ < T;) {
			System.out.println("graph " + t);
			int n = s.nextInt();
			int[][] a = new int[n][n];
			for (int i = 0; i < n; ++i) {
				int x = s.nextInt() - 1;
				for (int m = s.nextInt(); m-- > 0;) {
					a[x][s.nextInt() - 1] = 1;
				}
			}
			for (int v, c; (v = s.nextInt()) + (c = s.nextInt()) > 0;) {
				List<Integer> result = new ArrayList<Integer>();
				if (c == 0) {
					Stack<Integer> stack = new Stack<Integer>();
					stack.push(v - 1);
					while (!stack.isEmpty()) {
						int i = stack.pop();
						result.add(i + 1);
						for (int j = n; j-- > 0;) {
							if (!result.contains(j + 1) && !stack.contains(j)
									&& a[i][j] > 0) {
								stack.push(j);
							}
						}
					}
				} else {
					Queue<Integer> queue = new LinkedList<Integer>();
					queue.add(v - 1);
					while (!queue.isEmpty()) {
						int i = queue.poll();
						result.add(i + 1);
						for (int j = 0; j++ < n;) {
							if (!result.contains(j) && !queue.contains(j - 1)
									&& a[i][j - 1] > 0) {
								queue.add(j - 1);
							}
						}
					}
				}
				System.out.println(result.toString()
						.replaceAll("[\\[\\],]", ""));
			}
		}
	}
}

→TLE
やっぱ標準ライブラリだと遅いか．
とりあえずスタックだけ配列で自作．

→TLE
当たり前だけどスタックだけじゃなくてキューも自作がいいか．

→TLE
そういえば入力にjava.util.Scanner使ってるので遅いか．
ついでに出力もSystem.out.println()だと遅いらしい．
参考：http://www.codechef.com/wiki/java#IO_in_Java
java.io.BufferedReaderとjava.io.PrintWriterに切り替える．

→TLE
配列とかのインスタンス生成コストも馬鹿にできないかな．
主だったものをクラス変数に移行させる．

→TLE
あー，そういえば隣接行列だと走査時間かかるか．隣接リストにしてみるか．
あと，関係ないと思っているけど，まだ使ってたjava.utilパッケージのものを排除．

→TLE
まだか．そういえば探索のときに，今自分のいる頂点がすでに答えの配列に
入ってるかどうかを確認するのに全部なめてたけど，使用未使用の判定は
頂点数確保したboolean配列でO(1)で行けるんじゃないの．

→WA
やっとスタート地点に立った気がする．
しかしなんでWAだろうか．シンプルに実装してるから方法自体は間違ってないはずだからバグかな．
いろいろ検証．
問題にはグラフは双方向って明示してないけど隣接だから関係ないよな．
探索順番って普通小さい数字でナンバリングされた頂点からのはずだけど，
入力そのままだと昇順になってない？違う．
なんとなく自作のスタックキューと結果の格納部分をクラス化．

ここらへんでのコード

import java.io.*;

public class Main {
	static int[][] a = new int[1001][1000];
	static int n = 0;
	static Stack stack = new Stack();
	static Queue queue = new Queue();
	static Result result = new Result();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		for (int T = new Integer(br.readLine()), t = 0; t++ < T;) {
			pw.println("graph " + t);
			input(br);
			for (String str; (str = br.readLine()).charAt(0) != 48;) {
				String[] sp = str.split(" ");
				result.init();
				stack.init();
				queue.init();
				if (sp[1].equals("0")) {
					stack.push(new Integer(sp[0]));
					dfs();
				} else {
					queue.add(new Integer(sp[0]));
					bfs();
				}
				result.print(pw);
			}
		}
		pw.close();
	}
	
	private static void bfs() {
		while (result.size()< n && !queue.isEmpty()) {
			int i = queue.poll();
			if (!result.isUsed(i)) {
				result.add(i);
				for (int j=1;j<=a[i][0];++j) {
					if (!result.isUsed(a[i][j])) {
						queue.add(a[i][j]);
					}
				}
			}
		}
	}

	private static void dfs() {
		while (result.size() < n && !stack.isEmpty()) {
			int i = stack.pop();
			result.add(i);
			for (int j = a[i][0]+1; j-- > 1;) {
				if (!result.isUsed(a[i][j])) {
					stack.push(a[i][j]);
				}
			}
		}
	}
	
	private static class Stack{
		int[] stack = new int[1000000];
		int p = 0;
		public void push(int value){
			stack[p++]=value;
		}
		public int pop(){
			return stack[--p];
		}
		public void init(){
			p=0;
		}
		public boolean isEmpty(){
			return p==0;
		}
	}
	
	private static class Queue{
		int[] queue = new int[1000000];
		int p = 0, e=0;
		public void add(int value){
			queue[e++]=value;
		}
		public int poll(){
			return queue[p++];
		}
		public void init(){
			p=0;e=0;
		}
		public boolean isEmpty(){
			return p==e;
		}
	}
	
	private static class Result{
		int[] result = new int[1000];
		int rp = 0;
		boolean[] used = new boolean[1001];

		public void add(int value){
			result[rp++]=value;
			used[value]=true;
		}

		public boolean isUsed(int j){
			return used[j];
		}
		
		public void init(){
			rp=0;
			java.util.Arrays.fill(used, false);
		}
		public void print(PrintWriter pw) {
			pw.print(result[0]);
			for (int i = 1; i < rp; ++i) {
				pw.print(" " + result[i]);
			}
			pw.println();
		}
		
		public int size(){
			return rp;
		}
	}
	
	private static void input(BufferedReader br) throws IOException {
		n = new Integer(br.readLine());
		for (int i = 0; i < n; ++i) {
			String[] sp = br.readLine().split(" ");
			int x = new Integer(sp[0]);
			int m=new Integer(sp[1]);
			a[x][0] = m;
			for (int j=1; j <= m;++j) {
				a[x][j]=new Integer(sp[j + 1]);
			}
		}
	}
}

→WA→WA→WA
わからんのでググってみる．
参考になりそうなフォーラム発見．
http://www.spoj.pl/forum/viewtopic.php?f=41&t=3063&p=3218&hilit=TDBFS#p3218
そういやキュー使わなくても結果にそのままつっこめばいいのか．DFSはやっぱ再帰か．
とりあえずここにある内容をそのままJavaに落としてみる．

→WA
へー，再帰で書いてもJavaのヒープ使いきらないな，今までは引数に配列指定してたからか？
いやそうじゃなくて，なぜWAだろ．
うーんわからん．そういや結果出力用の配列初期化してないな．
現在指してる部分以外は関係ないはずだけど変な出力が混ざってるかもしれないので
初期化して，初期化された値だったは出力しないようにした．

→AC
…え？

出力にゴミが混ざってたのか？よくわからん．まあ，いいか．
入力の部分をちょこっと高速化して終了．
最終的に7sになった．

以下提出コード．

import java.io.*;

public class Main {
	static int[][] a = new int[1001][1000];
	static int n = 0;
	static Result result = new Result();

	public static void main(String[] args) throws Exception {
		PrintWriter pw = new PrintWriter(System.out);
		for (int T = next(), t = 0; t++ < T;) {
			pw.println("graph " + t);
			input();
			for (int v,c;(v=next())+(c=next())!=0;) {
				result.init();
				result.add(v);
				if (c==0) {
					dfs(v);
				} else {
					bfs();
				}
				result.print(pw);
			}
		}
		pw.close();
	}

	private static void dfs(int i) {
		if (result.size() == n + 1) {
			return;
		}
		for (int j = 1; j <= a[i][0]; ++j) {
			if (!result.isUsed(a[i][j])) {
				result.add(a[i][j]);
				dfs(a[i][j]);
			}
		}
	}

	private static void bfs() {
		int p = 0;
		while (result.size() < n + 1 && p < n + 1) {
			int i = result.get(p++);
			for (int j = 1; j <= a[i][0]; ++j) {
				if (!result.isUsed(a[i][j])) {
					result.add(a[i][j]);
				}
			}
		}
	}

	private static class Result {
		int[] result = new int[1000];
		int rp = 0;
		boolean[] used = new boolean[1001];

		public void add(int value) {
			result[rp++] = value;
			used[value] = true;
		}

		public boolean isUsed(int j) {
			return used[j];
		}

		public void init() {
			rp = 0;
			java.util.Arrays.fill(result, 0);
			java.util.Arrays.fill(used, false);
		}

		public void print(PrintWriter pw) {
			pw.print(result[0]);
			for (int i = 1; i < rp; ++i) {
				if (result[i] != 0) {
					pw.print(" " + result[i]);
				}
			}
			pw.println();
			pw.flush();
		}

		public int size() {
			return rp;
		}

		public int get(int i) {
			return result[i];
		}
	}

	private static void input() throws Exception {
		n = next();
		for (int i = 0; i < n; ++i) {
			int x = next();
			int m = next();
			a[x][0] = m;
			for (int j = 1; j <= m; ++j) {
				a[x][j] = next();
			}
		}
	}
	static int next() throws Exception {
		int result = 0;
		int b = ' ';
		for (; b == '\n' || b == ' ';) {
			b = System.in.read();
		}
		for (; '0' <= b && b <= '9';) {
			result = result * 10 + b - '0';
			b = System.in.read();
		}
		return result;
	}

}