Suppose you are given a text file containing pairs of city names, one
pair per line,
with the names on each line separated by a comma. The file might look
something like:

Philadelphia, Pittsburgh
Boston, New York
Philadelphia, New York
Los Angeles, San Diego
New York, Croton-Harmon
St. Petersburg, Tampa

Each line of the file indicates that it is possible to travel between
the two
cities named. (More formally, if we think of the cities as nodes in a
graph, each
line of the file specifies an edge between two nodes.)

In the example above it is possible to travel between Boston and New
York, and also
between New York and Philadelphia and between Philadelphia and
Pittsburgh, so it
follows that Boston and Pittsburgh are connected. On the other hand,
there is no
path between Boston and Tampa, so they are not connected.

---

Write a Java(r) program, called "Connected", that reads in such a file
and
outputs whether two specified cities are connected. The program will be
invoked
from the command line as:

java Connected <filename> <cityname1> <cityname2>

and will output a single line stating:

yes or no


Here are some sample interactions, assuming the example file above is
named
"cities.txt".

> java Connected cities.txt "New York" Boston
yes
> java Connected cities.txt Boston Pittsburgh
yes
> java Connected cities.txt Boston Tampa
no
> java Connected cities.txt Boston Ypsilanti
no

---

Notes
* Commas will not appear within city names in the file.
   For example, "Washington, D.C." will not appear in the file as a
city
name.
* You can depend on command-line quoting for cities with spaces in
their names,
   like "New York". This should, thus, require no extra code on your
part.
* Your choice of algorithms and data structures should allow the
program to handle
   arbitrarily large files reasonably efficiently. You can, however,
assume that
  the file will fit in memory.
* The program is permitted to return any or no output when given a
malformed input
   file or malformed command line.
* If a city is not in the file, then it is connected to no other city.

你要人帮你做题，也要给点诚意吧？

等过几天才考虑要不要做

the art of programming, 书上的练习题吧，呵呵。

题目很简单，好像以前见过。主要是考察你的编程习惯，注意细节就没什么问题了。

写了一个，简单测试没有问题，但总觉得如果城市和道路数量比较多的时候，运算时间会急剧增加。另外，对保存地图的数据结构也不满意，应该有更好的方式。

import java.io.*;
import java.util.*;

class Status {
  static final int UNVISITED = 0;
  static final int VISITING = 1;
  static final int VISITED = 2;
}

class City {
  private String name;
  private int status = Status.UNVISITED;

  public City(String name) {
    this.name = name;
  }

  public String getName() {
    return name;
  }

  public int getStatus() {
    return status;
  }

  public void setStatus(int status) {
    this.status = status;
  }

  public boolean equals(Object o) {
    return name.toLowerCase().equals(((City)o).getName().toLowerCase());
  }

  public int hashCode() {
    return name.hashCode();
  }
}

class Neighbours {
  private City rootCity;
  private Set<City> neighbourCities = new HashSet<City>();

  public Neighbours(City rootCity) {
    this.rootCity = rootCity;
  }

  public City getRootCity() {
    return rootCity;
  }

  public void addNeighbourCity(City city) {
    neighbourCities.add(city);
  }

  public Set<City> getNeighbourCities() {
    return neighbourCities;
  }
}

public class Connected {
  private Map<City,Neighbours> map = new HashMap<City,Neighbours>();
  private static City startCity, endCity;
  private boolean connected;

  boolean init(String fileName, String start, String end) {
    startCity = new City(start);
    endCity = new City(end);

    File file = new File(fileName);
    if (!file.exists()) {
      System.out.println("File "+fileName+" doesn't exist.");
      return false;
    }

    try {
      BufferedReader in = new BufferedReader(new FileReader(file));
      String s;
      while((s = in.readLine())!= null) {
        String[] cities = s.split(",");
        if (cities.length==2) {
          // System.out.println(cities[0]+","+cities[1]);
          City city1 = new City(cities[0].trim());
          City city2 = new City(cities[1].trim());

          /**
           * Make sure there is only one object for one city
           */
          if (city1.equals(startCity)) city1 = startCity;
          if (city2.equals(startCity)) city2 = startCity;
          if (map.containsKey(city1)) city1 = map.get(city1).getRootCity();
          else map.put(city1,new Neighbours(city1));
          if (map.containsKey(city2)) city2 = map.get(city2).getRootCity();
          else map.put(city2,new Neighbours(city2));

          /**
           * Save road info
           */
          map.get(city1).addNeighbourCity(city2);
          map.get(city2).addNeighbourCity(city1);
        }
      }
      in.close();

    }
    catch (IOException ioe) {
      System.out.println("Invalid file content.");
      return false;
    }

    return true;
  }

  boolean search(City rootCity) {
    // System.out.println(rootCity.getName());
    rootCity.setStatus(Status.VISITING);
    Set<City> neighbourCities
        = map.get(rootCity).getNeighbourCities();
    Iterator<City> it = neighbourCities.iterator();
    while (it.hasNext()) {
      City city = it.next();
      if (city.getStatus()==Status.UNVISITED) {
        if (city.equals(endCity) || search(city)) {
          System.out.print(city.getName()+">");
          return true;
        }
      }
    }
    rootCity.setStatus(Status.VISITED);

    return false;
  }

  public static void main(String[] args) {
    Connected connected = new Connected();

    if (args.length < 3 ) {
      System.out.println("Too few arguments!");
    } else if (connected.init(args[0], args[1], args[2])) {
      if (connected.search(startCity)) {
        System.out.println(startCity.getName()+" - Yes");
      } else System.out.println("No");
    } else System.out.println("Illegal arguments!");
  }
}

public class Connected {
	public static void main(String []args){
		ConnectionMap map = null;
		if (args.length<3){
			System.out.println("no");
			System.exit(0);
		}else {
			map = MapParser.parse(args[0]);
			if (map.canConnect(args[1].toLowerCase(),args[2].toLowerCase())){
					System.out.println("yes");
			}else{
					System.out.println("no");
			}
			System.exit(0);
		}
	}
}

 

public class ConnectionMap extends Hashtable{
	public boolean canConnect(String fromCity,String toCity){
		if (this.containsKey(fromCity) && this.containsKey(toCity))
		{
			return this.connect(fromCity, toCity);
		}
		return false;//cities are not on the map;
	}
	private boolean connect(String fromCity,String toCity){
				boolean result = false;
				String nextCity = null;
				Set traveloptions = (Set)this.get(fromCity);
				Iterator ti =traveloptions.iterator();
				while (ti.hasNext()){
						TravelPath path =(TravelPath)ti.next();
						if (path.isTraveled()) continue;
						nextCity = path.travleFrom(fromCity);
						result = toCity.equalsIgnoreCase(nextCity) || result ||this.connect(nextCity, toCity);
if(result) break;}
				 
				return result;
	}
	
}

 

 

public class MapParser {	public static ConnectionMap parse(String fileName){
	
		ConnectionMap map = new ConnectionMap();
		try {  
		      BufferedReader in = new BufferedReader(new FileReader(fileName));  
		      String s;  
		      while((s = in.readLine())!= null) {  
		        String[] cities = s.split(",");  
		        if (cities.length==2) {  
	    			String city1 =cities[0].trim().toLowerCase();
	    			String city2 =cities[1].trim().toLowerCase();
	    			TravelPath path = new TravelPath(city1,city2);
		        	for (int i = 0 ;i<cities.length;i++){
		        		String key = cities[i].trim().toLowerCase();
		        		Set value = map.containsKey(key)?(Set) map.get(key) :new HashSet();
		        		value.add(path);
		        		map.put(key, value);
		        		} 	
		        }
		      }  
		      in.close();  
		    }  
		    catch (IOException ioe) {  
		      System.out.println("Invalid file content.");  
		    }
		    System.out.println(map.size());
		    Enumeration citis = map.keys();
		    while (citis.hasMoreElements()){
		    	String city = (String)citis.nextElement();
		    	System.out.println(city+":"+map.get(city));
		    }
		    return map;
	}
}

 

public class TravelPath {	private String city1;
	private String city2;
	private int travelcount = 0;
	
	
	 public boolean equals(Object o) {  
		 TravelPath other = (TravelPath)o;
		 String otherCity1 = other.getCity1();
		 String otherCity2 = other.getCity2();
		 return 
		 (this.city1.equalsIgnoreCase(otherCity1) && this.city2.equalsIgnoreCase(otherCity2))
		 ||
		 (this.city2.equalsIgnoreCase(otherCity1) && this.city1.equalsIgnoreCase(otherCity2));
		 
	 }  
		  
	public int hashCode() {  
	  return city1.hashCode()+city2.hashCode();  
	}  
	public TravelPath(String city1,String city2){
		
		this.city1 = city1;
		this.city2 = city2;
		 
	}
	public String travleFrom(String fromCity){
		
		if (this.city1.equalsIgnoreCase(this.city2)) return null;
		if (fromCity!=null) {
		travelcount++;
		if (fromCity.equalsIgnoreCase(city1)) return city2;
		if (fromCity.equalsIgnoreCase(city2)) return city1;
		}return null;
		
	}
	public boolean isTraveled(){
		
		return (this.travelcount >0);
	}
	
	public boolean hasCity(String city){
		return city!=null?city.equalsIgnoreCase(this.city1)||city.equalsIgnoreCase(city2):false;
	}

	public String getCity1() {
		return city1;
	}

	public String getCity2() {
		return city2;
	}
	public String toString(){
		return city1+"<->"+city2;
	}
}

 

看看不同的思路，跟你自己的大同小异。抽象的角度不一样。

三人行，必有我师。谢谢。
我开始的思路部分地与你的接近，但后来改了。
本来也想用字符串表示城市，但考虑到大小写的问题，为避免map中的key出现歧义，就放弃了。

你自己的写法也考虑到了大小写啊。
我没有具体对比过，你可以看看那个更适合你。