Taro's Obsession(AOJ No.0119)
リポジトリ
ジャッジできるようになっていたので解いた。
Taro's Obsession(AOJ No.0119)
登場人物数m(1〜mのidが振られている)とn個の証言が与えられる。
証言は「人物xが人物yより先に部屋に入った」という形式。
部屋に入った順番としてあり得る物を一つ答える。
制約
矛盾する証言は無い。
アルゴリズム
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); } } } } }