PKU 2491-Scavenger Hunt

問題概要

ある街から街へと一本道で移動した人がいる．
不親切なことにその人は移動元の街と移動先の街はメモしたもののその順番はメモしなかった．
街を回った順番を求めよ．

解法

グラフを作って調べる

実装(Java)

import java.util.*;
import java.math.*;
import java.io.*;
import java.util.regex.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.lang.System.*;

public class Main {
	Scanner cin;
	List<String> city;
	int getCityNo(String s){
		if(city.indexOf(s)!=-1)return city.indexOf(s);
		city.add(s);
		return city.indexOf(s);
	}
	void run(){
		cin=new Scanner(System.in);
		int TC;
		TC=cin.nextInt();
		for(int tc=1;tc<=TC;tc++){
			int V;
			V=cin.nextInt();
			int []next=new int[V];

			int []in=new int[V];
			city=new ArrayList<String>();
			printf("Scenario #%d:\n",tc);

			for(int i=0;i<V-1;i++){
				int a,b;
				a=getCityNo(cin.next());b=getCityNo(cin.next());
				next[a]=b;
				in[b]++;
			}
			for(int i=0;i<V;i++){
				if(in[i]==0){
					int now=i;
					for(int j=0;j<V;j++){
						printf("%s\n",city.get(now));
						now=next[now];
					}
				}
			}

			printf("\n");
		}
	}

	void printf(String format,Object... args){
		System.out.printf(format, args);
	}

	public static void main(String[] args) {
		new Main().run();
	}

}