老外的面试题，要求两天内完成

public class City {
	
	private String name = "ERROR";
	private List<City> neighbours = new ArrayList<City>();
	
	private static Set<City> visitedCity;
	
	City(String name) {
		this.name = name;
	}
	
	public void addNeighbour(City aNeighbour) {
		this.neighbours.add(aNeighbour);
	}
	
	public String canFindPath2(City cityB) {
		 visitedCity = new HashSet<City>();
		 boolean result = canFindPath(this, cityB);
		 visitedCity = null;
		return result ? "YES" : "NO";
	}
	
	private boolean canFindPath(City start,City end) {
	
		
		for(City aNeighbour : this.neighbours) {
			if(aNeighbour.equals(start))
				continue;
			
			if(aNeighbour == end)
				return true;
			
			if(visitedCity.contains(aNeighbour)){
				continue;
			}else {
				visitedCity.add(aNeighbour);
			}
			return aNeighbour.canFindPath(start, end);
		}
		return false;
	}
	
	@Override
	public String toString() {
		return name;
	}

	@Override
	public boolean equals(Object obj) {
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		final City other = (City) obj;
		if (!name.equals(other.name))
			return false;
		return true;
	}
}

public class PathMananger {
	
	public List<City> cities = new ArrayList<City>();
	
	public static PathMananger reg = new PathMananger();
	
	public static PathMananger INSTANCE() {
		return reg;
	}
	
	public PathMananger() {
		try {
			loadInfo();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	public String canConnected(String startCityName,String endCityName) {
		City cityA = this.getCity(startCityName);
		return cityA.canFindPath2(this.getCity(endCityName));
	}
	
	
	private void loadInfo() throws IOException {
		File file = new File("paths.txt");
		BufferedReader reader = new BufferedReader(new FileReader(file));
		String tempLine = null;
		while((tempLine = reader.readLine())  != null) {
			String[] twoCityName = tempLine.split(",");
			//TODO E
			reg.addPath(twoCityName[0], twoCityName[1]);
		}
		reader.close();
	}
	
	private City getCity(String name) {
		for(City aCity : cities) {
			if(aCity.toString().equals(name))
				return aCity;
		}
		City newCity = new City(name);
		cities.add(newCity);
		return newCity;
	}
	
	private void addPath(String start,String end) {
		City cityA = this.getCity(start);
		City cityB = this.getCity(end);
		cityA.addNeighbour(cityB);
		cityB.addNeighbour(cityA);
	}
}

public class Main {
	
	public static void main(String[] args) {
		System.out.println(PathMananger.INSTANCE().canConnected("杭州","乌鲁木齐"));
	}
}

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * 
 * @author lin5061@163.com
 * @date 2008-6-16 上午03:02:25
 */
public class Connected {

	//城市列表
	private static Map<String, LinkedList<String>> cityLines = new HashMap<String, LinkedList<String>>();

	//处理过的城市的列表
	private static List<String> processList = new ArrayList<String>();

	//是否找到
	private static boolean found = false;

	//构造结构
	private static void addCityLines(String c1, String c2) {
		if (cityLines.containsKey(c1)) {
			LinkedList<String> ll = cityLines.get(c1);
			if (!ll.contains(c2)) {
				ll.add(c2);
			}
		} else {
			LinkedList<String> ll = new LinkedList<String>();
			ll.add(c2);
			cityLines.put(c1, ll);
		}

		if (cityLines.containsKey(c2)) {
			LinkedList<String> ll = cityLines.get(c2);
			if (!ll.contains(c1)) {
				ll.add(c1);
			}
		} else {
			LinkedList<String> ll = new LinkedList<String>();
			ll.add(c1);
			cityLines.put(c2, ll);
		}
	}

	//读文件
	private void readFile(String fileName) throws IOException {
		File file = new File(fileName);
		if (!file.exists()) {
			System.out.println("file [" + fileName + "] is not exists");
			return;
		}
		BufferedReader in = new BufferedReader(new FileReader(file));
		String s;
		while ((s = in.readLine()) != null) {
			String[] towCitys = s.split(",");
			if (towCitys == null || towCitys.length != 2) {
				System.out.println("Format error!");
				return;
			}
			Connected.addCityLines(towCitys[0], towCitys[1]);
		}
		in.close();
	}

	//查找
	private static void isReach(String c1, String c2) {
		
		//如果c1等于c2 则肯定可以到达 这是防止第一次就传两个一样的值
		if (c2.equals(c1)) {
			found = true;
			return;
		}

		//如果处理过的列表中存在c2了，则跳出本次递归
		if (processList.contains(c1)) {
			return;
		}

		//如果总列表中不包含c1或c2,则跳出递归 第一次就执行了
		if (!cityLines.containsKey(c1)) {
			// System.out.println("no");
			return;
		}

		if (!cityLines.containsKey(c2)) {
			// System.out.println("no");
			return;
		}

		//将c1和c2放入处理过列表
		processList.add(c1);
		processList.add(c2);

		//如果c1的值列表里存在c2,说明c1能到达c2
		LinkedList<String> tempList = cityLines.get(c1);
		if (tempList.contains(c2)) {
			found = true;
			// System.out.println("yes");
			return;
		}

		//如果c2的值列表里存在c1,说明c1能到达c2
		LinkedList<String> tempList2 = cityLines.get(c2);
		if (tempList2.contains(c1)) {
			found = true;
			// System.out.println("yes");
			return;
		}

		//循环处理c1的值列表
		for (int i = 0; i < tempList.size() && !found; i++) {
			//递归处理
			isReach(tempList.get(i), c2);
		}

	}

	public static void main(String[] args) throws IOException {
//		if (args == null || args.length != 3) {
//			System.out.println("input error!");
//			return;
//		}
//
//		Connected c = new Connected();
//		c.readFile(args[0]);
//		isReach(args[1], args[2]);

		Connected c = new Connected();
		c.readFile("c:\\city.txt");
		isReach("a", "g");
		if (found) {
			System.out.println("yes");
		} else {
			System.out.println("no");
		}
	}
}

import java.util.Set;

public interface Routable{
	public String getName();
	public void addSibling(Routable route);
	public Set<Routable> getSiblings();
	public boolean canArrive(Routable destRoute);
	public boolean isChecked();
	public void setChecked(boolean checked);
}

import java.util.HashSet;
import java.util.Set;




public class City implements Routable{
	private Set<Routable> siblings=new HashSet<Routable>();
	private String name;
	private boolean checked=false;
	
	public City(String name){
		this.name=name;
	}
	
	@Override
	public void addSibling(Routable route) {
		if(!siblings.contains(route)){
			siblings.add(route);
			route.addSibling(this);
		}
	}
	
	public Set<Routable> getSiblings(){
		return this.siblings;
	}

	@Override
	public boolean canArrive(Routable destRoute) {
		setChecked(true);
		if(siblings.contains(destRoute)){
			return true;
		}
		for(Routable r:siblings){
			if(r.isChecked()){
				continue;
			}
			if(r.canArrive(destRoute)){
				return true;
			}
		}
		return false;
	}

	@Override
	public String getName() {
		return name;
	}
	
	public boolean equals(Object obj) {
		if(obj==null || !(obj instanceof City)){
			return false;
		}
		if(this==obj){
			return true;
		}
		City c=(City)obj;
		return c.getName().equals(this.name);
	}
	
	
	public int hashCode(){
		int hash = 1;
	    hash = hash * 31 + name==null ? 0 : name.hashCode();
	    return hash;
	}
	
	public String toString(){
		return this.name;
	}

	@Override
	public boolean isChecked() {
		return checked;
	}
	
	public void setChecked(boolean checked){
		this.checked=checked;
	}

}

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Router {
	private String fileName;
	private Map<String,Routable> cities=new HashMap<String,Routable>();
	
	public Router(String fileName){
		this.fileName=fileName;
	}
	
	//initialize route table from file
	public void initialize() throws IOException{
		FileReader fr=new FileReader(fileName);
		BufferedReader bf=new BufferedReader(fr);
		String line=null;
		try{
		while((line=bf.readLine())!=null){
			String[] cs=line.split(",");
			String c1=cs[0].trim();
			String c2=cs[1].trim();
			Routable city1=getRouteByName(c1);
			Routable city2=getRouteByName(c2);
			if(city1==null){
				city1=new City(c1);
				cities.put(city1.getName(),city1);
			}
			if(city2==null){
				city2=new City(c2);
				cities.put(city2.getName(),city2);
			}
			city1.addSibling(city2);
		}
		System.out.println("@@@initialize ok!");
		printCitiesMap();
		}catch(IOException x){
			x.printStackTrace();
			throw x;
		}finally{
			try{
				bf.close();
			}catch(Exception x){
				
			}
		}
	}
	
	//check connected
	public boolean isConnected(String cityName1,String cityName2) throws CityNotFoundException{
		Routable city1=getRouteByName(cityName1);
		Routable city2=getRouteByName(cityName2);
		if (city1==null){
			throw new CityNotFoundException("city " + cityName1 + " is not found");
		}
		if (city2==null){
			throw new CityNotFoundException("city " + cityName2 + " is not found");
		}
		return city1.canArrive(city2);
	}
	
	//print route table
	private void printCitiesMap(){
		Collection<Routable> c=cities.values();
		int cityNum=1;
		System.out.println("@@@CityMap:");
		System.out.println("===========================================");
		for(Routable c1:c){
			System.out.println("@city" + cityNum + "=" + c1);
			Set<Routable> siblings=c1.getSiblings();
			for(Routable r:siblings){
				System.out.println("    -sibling city=" + r);
			}
			cityNum++;
		}
		System.out.println("===========================================");
	}
	
	private Routable getRouteByName(String name){
		return cities.get(name);
	}
	
	//reset route table, make refinding available
	private void reset(){
		Collection<Routable> c=cities.values();
		for(Routable c1:c){
			c1.setChecked(false);
		}
	}
	
}

import java.io.IOException;

public class Connected {
	public static void main(String[] args){
		if(args==null || args.length!=3){
			System.out.println("Please run as 'java Connected <filename> <cityname1> <cityname2> '");
			return;
		}
		String fileName=args[0];
		String cityName1=args[1];
		String cityName2=args[2];
		System.out.println("@@@To find connecting between "+ args[1] + " and " + args[2]);
		Router router=new Router(fileName);
		try {
			router.initialize();
		} catch (IOException e) {
			e.printStackTrace();
			System.err.println("bad file found!");
			return;
		}
		try {
			System.out.println("");
			System.out.println("@@@find result is :");
			if (router.isConnected(cityName1,cityName2)) {
				System.out.println("yes");
			} else {
				System.out.println("no");
			}
		} catch (CityNotFoundException x) {
			//x.printStackTrace();
			//System.err.println(x.getMessage());
			System.out.println("no");
		}
	}
	
}

public class CityNotFoundException extends Exception{
	public CityNotFoundException(){
		super();
	}
	
	public CityNotFoundException(String msg){
		super(msg);
	}
}

package eli.math;

import java.io.FileReader;
import java.io.IOException;
import java.io.LineNumberReader;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Connected {
	@SuppressWarnings("unchecked")
	protected Set<Set<String>> calcKinds(Set<Set<String>> set) {
		Set<Set<String>> result = new HashSet<Set<String>>(0);
		Set[] arr = new Set[set.size()];
		set.toArray(arr);
		for (int i = arr.length - 1; i > 0; i--) {
			for (int j = i - 1; j >= 0; j--) {
				if (arr[i] != null) {
					for (Iterator it = arr[i].iterator(); it.hasNext();) {
						if (arr[j].contains(it.next())) {
							arr[j].addAll(arr[i]);
							arr[i] = null;
							break;
						}
					}
				}
			}
		}
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] != null) {
				result.add(arr[i]);
			}
		}
		return result;
	}

	public boolean isConnected(Set<Set<String>> cities, String beginCity,
			String endCity) {
		Set<Set<String>> set = calcKinds(cities);
		for (Iterator<Set<String>> it = set.iterator(); it.hasNext();) {
			Set<String> set2 = it.next();
			if (set2.contains(beginCity) && set2.contains(endCity)) {
				return true;
			}
		}
		return false;
	}

	protected Set<Set<String>> readFromFile(String file) throws IOException {
		Set<Set<String>> cities = new HashSet<Set<String>>(0);
		LineNumberReader fileReader = new LineNumberReader(new FileReader(file));
		Set<String> tmp = null;
		for (String line = fileReader.readLine(); line != null; line = fileReader
				.readLine()) {
			String[] arr = line.split(",");
			if (arr.length == 2) {
				tmp = new HashSet<String>(0);
				tmp.add(arr[0].trim());
				tmp.add(arr[1].trim());
				cities.add(tmp);
			}
		}
		return cities;
	}

	public static void main(String[] args) {
		Cities cities = new Cities();
		try {
			if (args.length == 3) {
				boolean bool = cities.isConnected(cities.readFromFile(args[0]),
						args[1], args[2]);
				System.out.println(bool ? "yes" : "no");
			} else {
				throw new IllegalArgumentException();
			}
		} catch (Exception e) {
			System.out.println("Usage: java " + Connected.class.getName()
					+ " <filename> <cityname1> <cityname2> ");
		}
	}
}

//  从今天开始使用这个新马甲了

//  我看题目只是需要计算yes or no，那可以大大简化
//  把city看成node
//  能够连通的nodes组成连通图
//  这样所有的city就一定属于有限的几个连通图了
//  计算题目就直接转换为两个city是否属于同一个连通图
//  另外为了便于合并连通图，我把连通图多作了一层间接指引, 即:
//      cityGraphIDMap[cityName] --> unionIndex
//      unionIDs[unionIndex] --> unionID
//      unionID相同的认为是同一个连通图


import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Connected {
    Map<String, Integer> cityGraphIDMap = new HashMap<String, Integer>();
    int[] unionIDs = null;  //  unionIDs[unionIndex] --> unionID

    int nextUnionIndex;

    String cityName1;
    String cityName2;

    Connected(String cityName1, String cityName2) {
        this.cityName1 = cityName1;
        this.cityName2 = cityName2;
        this.nextUnionIndex = 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader cityFile = new BufferedReader(new FileReader(new File(args[0])));
        String cityName1 = args[1];
        String cityName2 = args[2];
        new Connected(cityName1, cityName2).start(cityFile);
    }

    //  main entry
    void start(BufferedReader cityFile) throws IOException {
        if (cityName1.equals(cityName2) || loadFile(cityFile)) {
            System.out.println("yes");
        } else {
            System.out.println("no");
        }
    }

    //  return whether cityName1 connected with cityName2
    boolean loadFile(BufferedReader cityFile) throws IOException {
        for (; ;) {
            String line = cityFile.readLine();
            if (line == null)
                break;

            int pos = line.indexOf(',');
            if (pos > 0) {
                connect(line.substring(0, pos), line.substring(pos + 1));
                // 这里也可以在每读取一行就检查一下isConnected
            }
        }
        return isConnected();
    }

    void connect(String city1, String city2) {
        if (city1.equals(city2))
            return;

        Integer unionIndex1 = cityGraphIDMap.get(city1);
        Integer unionIndex2 = cityGraphIDMap.get(city2);

        if (unionIndex1 != null) {
            if (unionIndex2 != null) {
                if (!isSameUnion(unionIndex1, unionIndex2))     // 不同的连通图
                    combineUnion(unionIndex1, unionIndex2);
            } else {
                cityGraphIDMap.put(city2, unionIndex1);  // 把city2 加入到连通图id1中
            }
        } else {
            if (unionIndex2 != null) {
                cityGraphIDMap.put(city1, unionIndex2);  // 把city1 加入到连通图id2中
            } else {
                createNewUnion(city1, city2);
            }
        }
    }

    //  合并连通图
    void combineUnion(int unionIndex1, int unionIndex2) {
        int unionID1 = unionIDs[unionIndex1];
        unionIDs[unionIndex2] = unionID1;
    }

    //  创建新的连通图
    void createNewUnion(String city1, String city2) {
        final int newUnionIndex = nextUnionIndex;
        final int newUnionID = newUnionIndex + 1;

        if (unionIDs == null)
            unionIDs = new int[newUnionIndex + 1];
        else
            unionIDs = Arrays.copyOf(unionIDs, newUnionIndex + 1);

        cityGraphIDMap.put(city1, newUnionIndex);
        cityGraphIDMap.put(city2, newUnionIndex);
        unionIDs[newUnionIndex] = newUnionID;

        nextUnionIndex++;
    }


    //  return whether cityName1 connected with cityName2
    boolean isConnected() {
        Integer index1 = cityGraphIDMap.get(cityName1);
        if (index1 == null)
            return false;

        Integer index2 = cityGraphIDMap.get(cityName2);
        if (index2 == null)
            return false;

        return isSameUnion(index1, index2);
    }

    boolean isSameUnion(int index1, int index2) {
        return index1 == index2 || unionIDs[index1] == unionIDs[index2];
    }
}