CareerCup

#include<iostream>
#include<map>
#include<vector>

using namespace std;

int main()
{
	vector<string> v;
	v.push_back("A");
	v.push_back("C");
	v.push_back("D");
	v.push_back("E");
	v.push_back("C");
	v.push_back("D");
	v.push_back("E");
	v.push_back("F");
	
	map<string,string> m;
	for(int i=0;i<v.size();i +=2)
		m.insert(make_pair(v[i],v[i+1]));
	
	map<string,string>::iterator it = m.begin();
	string nextKey = it->first;
	int size = m.size();
	string route = "";
	while(size--)
	{
		it = m.find(nextKey);
		if(it != m.end())
		{
			nextKey = it->second;
			cout<<it->first<<"->";
		}
		else
			break;
		
		
	}
cout<<it->second;

}

This is a topological sorting problem. Use the vector<String> to build the graph. Then do topological sorting on it. Below is my code. For more information, please visit my website: allenlipeng47.com/PersonalPage/index/view/105/nkey

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

public class TopogicalSorintDFS {

	public static void main(String[] args) {
		Vector<String> airports = new Vector<String>();
		airports.add("JFK");
		airports.add("LAX");
		airports.add("SNA");
		airports.add("RKJ");
		airports.add("LAX");
		airports.add("SNA");
		Vector<String> result = findPath(airports);
		System.out.println(result.toString());
	}

	public static Vector<String> findPath(Vector<String> airports) {
		Map<String, AirNode> nodes = new HashMap<String, AirNode>();
		// construct graph
		for (int i = 0; i < airports.size(); i += 2) {
			String from = airports.get(i);
			String to = airports.get(i + 1);
			if (!nodes.containsKey(from)) {
				nodes.put(from, new AirNode(from));
			}
			if (!nodes.containsKey(to)) {
				nodes.put(to, new AirNode(to));
			}
			nodes.get(from).outgoing.add(nodes.get(to));
		}
		Vector<String> result = new Vector<String>();
		HashSet<String> visited = new HashSet<String>();
		//start the dfs on graph
		for (AirNode node : nodes.values()) {
			dfs(node, visited, result);
		}
		return result;
	}

	public static void dfs(AirNode node, HashSet<String> visited,
			Vector<String> result) {
		if (visited.contains(node.airport)) {
			return;
		}
		visited.add(node.airport);
		for (AirNode curr : node.outgoing) {
			dfs(curr, visited, result);
		}
		result.insertElementAt(node.airport, 0);
	}
}

class AirNode {
	String airport;
	Set<AirNode> outgoing;

	public AirNode(String airport) {
		this.airport = airport;
		outgoing = new HashSet<AirNode>();
	}

	public boolean equals(Object obj) {
		if (obj == null) {
			return false;
		}
		if (this == obj) {
			return true;
		}
		if (obj instanceof AirNode) {
			AirNode node = (AirNode) obj;
			return this.airport.equals(node.airport);
		}
		return false;
	}

	public int hashCode() {
		return this.airport.hashCode();
	}
}

This is not DFS problemm. Shortest route might be different. Bellman Ford has to be used.