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

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Taro's Obsession(AOJ No.0119)

リポジトリ
ジャッジできるようになっていたので解いた。

Taro's Obsession(AOJ No.0119)

登場人物数m(1〜mのidが振られている)とn個の証言が与えられる。
証言は「人物xが人物yより先に部屋に入った」という形式。
部屋に入った順番としてあり得る物を一つ答える。
制約
矛盾する証言は無い。
 1\leq m \leq 20
 1\leq n \leq 100

アルゴリズム

y->xというエッジを持つグラフを作る。
出次数が0のノードがあれば、そのノードから出力し、それとつながっているエッジを削除する。
これをエッジが無くなるまで繰り返す。

コード

import java.util.*;
public class aoj0119 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int m = stdin.nextInt(), n = stdin.nextInt();
		@SuppressWarnings("unchecked") Set<Integer>[] list = new HashSet[m];
		for(int i = 0; i < m; ++i) list[i] = new HashSet<Integer>();
		for(int i = 0; i < n; ++i) {
			Integer dst = stdin.nextInt()-1, src = stdin.nextInt()-1;
			list[src].add(dst);
		}
		boolean flag = true;
		while(flag){
			flag = false;
			for(int i = 0; i < m; ++i){
				if(list[i] == null) continue;
				if(list[i].isEmpty()){
					flag = true;
					list[i] = null;
					System.out.println(i+1);
					for(int j = 0; j < m; ++j)
						if(list[j] != null && list[j].contains(i)) list[j].remove(i);
				}
			}
		}
	}
}