AOJ1134 Name the Crossing

問題リンク Name the Crossing

• 解法

「通りの名前」を頂点にしたグラフを作って解いていきます。
まず、XとYが違う方向の通りかを判定するためのグラフを作ります。これは色塗り問題と考えることができます。同じ色で塗られていたらそれは同じ方向です。ただし、YESと答えるためには、2つの通りの方向の違いが曖昧だとダメです。なので、違う連結成分に含まれているならばそれらはNOとなります。これは、違う連結成分に使う色を変えることで対処できます。
次は、水準の上下関係を表す有向グラフを作ります。B→Aという辺で、Aの水準がB以上であることを表します。A→B、B→Aの辺が張られていたら、AとBが同水準であることを表します。
入力のN個の情報から、そのままこの辺がN本引けます。
次にXとYの通りが同水準であるかどうかを全て判定します。通りの名前は高々200種類なので間に合います。
これでグラフは完成です。クエリで"X-Y"という入力が来たら、「XとYの色が確実に異なる」且つ「グラフ上でYの頂点からXの頂点へ行くことができる」が成り立つかを調べればいいです。

• ソース

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

//Name the Crossing
public class AOJ1134 {

	class R{
		int id, col;
		Set<Integer> adj, eq;
		boolean visit;
		public R(int id) {
			this.id = id;
			col = -1;
			eq = new HashSet<Integer>();
			adj = new HashSet<Integer>();
		}
		void color(int c){
			if(visit)return;
			col = c;
			visit = true;
			for(int v:adj)rs[v].color(c%2==0?(c+1):(c-1));
		}
		boolean reach(int g){
			if(id==g)return true;
			if(visit)return false;
			visit = true;
			for(int v:eq)if(rs[v].reach(g))return true;
			return false;
		}
	}
	
	int ID;
	Map<String, R> ref;
	Set<String> streets;
	String[] names;
	R get(String s){
		if(ref.containsKey(s))return ref.get(s);
		R res = new R(ID);
		names[ID] = s;
		rs[ID++] = res;
		ref.put(s, res);
		return res;
	}
	R[] rs;
	
	void reset(){
		for(int i=0;i<ID;i++)rs[i].visit = false;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			ID = 0;
			ref = new HashMap<String, R>();
			rs = new R[200];
			names = new String[200];
			streets = new HashSet<String>();
			while(n--!=0){
				String t = sc.next();
				streets.add(t);
				String s[] = t.split("-");
				R a = get(s[0]), b = get(s[1]);
				a.adj.add(b.id); b.adj.add(a.id);
				b.eq.add(a.id);
			}
			int col = 0;
			for(int i=0;i<ID;i++){
				if(rs[i].visit)continue;
				rs[i].color(col);
				col+=2;
			}
			int N =	ID;
			for(int i=0;i<N;i++)for(int j=i+1;j<N;j++){
				boolean C, D, E;
				C = false;
				D = E = true;
				for(int k=0;k<N;k++){
					if(k==i||k==j)continue;
					if(rs[i].adj.contains(k)&&rs[j].adj.contains(k))C = true;
					if(streets.contains(names[k]+"-"+names[i])&&streets.contains(names[j]+"-"+names[k]))D = false;
					if(streets.contains(names[i]+"-"+names[k])&&streets.contains(names[k]+"-"+names[j]))E = false;
					if(!D||!E)break;
				}
				if(C&&D&&E){
					R a = get(names[i]), b = get(names[j]);
					a.eq.add(b.id); b.eq.add(a.id);
				}
			}
			System.out.println(N);
			int m = sc.nextInt();
			while(m--!=0){
				String[] t = sc.next().split("-");
				R a = get(t[0]), b = get(t[1]);
				if(a.col==b.col||Math.abs(a.col-b.col)>=2||a.col==-1||b.col==-1){
					System.out.println("NO"); continue;
				}
				reset();
				System.out.println(b.reach(a.id)?"YES":"NO");
			}
		}
	}
	
	public static void main(String[] args) {
		new AOJ1134().run();
	}
}