Codeforces #29 (div2) C "Mail Stamps"

問題：http://codeforces.com/contest/29/problem/C

プラクティス．
隣接リストで辺を保持．一本道だから端はそれぞれ一回しか出現しない．

本番中は最後の経路出力の際にいったんListに貯めてたせいで，
たぶんList#contains(int)が激遅だったことによりテストケース14でTLE．

import java.util.*;
public class C_MailStamps {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		Map<Integer,List<Integer>>map=new HashMap<Integer,List<Integer>>();
		int n=s.nextInt();
		for(int i=0;i<n;++i){
			int x=s.nextInt(),y=s.nextInt();
			if(!map.containsKey(x)){
				map.put(x, new ArrayList<Integer>());
			}
			map.get(x).add(y);
			if(!map.containsKey(y)){
				map.put(y, new ArrayList<Integer>());
			}
			map.get(y).add(x);
		}
		int e=0;
		Set<Integer> set=new HashSet<Integer>();
		for(int key : map.keySet()){
			if(map.get(key).size()==1){
				set.add(e=key);
				break;
			}
		}
		System.out.print(e);
		for(;set.size()<n+1;){
			for(int i:map.get(e)){
				if(!set.contains(i)){
					set.add(e=i);
					System.out.print(" "+e);
					break;
				}
			}
		}
		System.out.println();
	}
}