Build Order
出处
You are given a list of projects and a list of projects and a list of dependencies (which is a list of pairs of projects, where the first project is dependent on the second project). All of a project's dependencies must be built before the project is. Find a build order that will allow the projects to be built. If there is no valid build order, return an error.
EXAMPLE
Input:
projects: a, b, c, d, e, f
dependencies: (d, a), (b, f), (d, b), (a, f), (c, d)
Output:
f, e, a, b, d, c
Solution
见 CC
Complexity
Code
Project[] findBuildOrder(String[] projects, String[][] dependencies){
Graph graph = buildGraph(projects, dependencies);
return orderProjects(graph.GetNodes());
}
Graph buildGraph(String projects, String[][] dependencies){
Graph graph = new Graph();
for (String project: projects){
graph.createNode(project);
}
for (String[] dependency: dependencies){
String first = dependency[0];
String second = dependency[1];
graph.addEdge(first, second);
}
return graph;
}
Project[] orderProjects(ArrayList<Project> projects){
Project[] order = new Project[projects.size()];
int endOfList = addNonDependent(order, projects, 0);
int toBeProcessed = 0;
while (toBeProcessed < order.length){
Project current = order[toBeProcessed];
if (current == null){
return null;
}
ArrayList<Project> children = current.getChildren();
for (Project child: children){
child.decrementDependencies();
}
endOfList = addNonDependent(order, children, endOfList);
toBeProcessed++;
}
return order;
}
int addNonDependent(Project[] order, ArrayList<Project> projects, int offset){
for (Project project: projects){
if (project.getNumberDependencies() == 0){
order[offset] = project;
offset++;
}
}
return offset;
}
class Graph {
private ArrayList<Project> nodes = new ArrayList<Project>();
private HashMap<String, Project> map = new HashMap<String, Project>();
public Project getOrCreateNode(String name){
if (!map.containsKey(name)){
Project node = new Project(name);
nodes.add(note);
map.put(name, node);
}
return map.get(name);
}
public void addEdge(String startName, String endName){
Project start = getOrCreateNode(startName);
Project end = getOrCreateNode(endName);
start.addNeighbor(end);
}
public ArrayList<Project> getNodes(){ return nodes;}
}
class Project{
private ArrayList<Project> children = new ArrayList<Project>();
private HashMap<String, Project> map = new HashMap<String, Project>();
private String name;
private int dependencies = 0;
public Project(String n) { name = n;}
public void addNeighbor(Project node){
if (!map.containsKey(node.getName())){
children.add(node);
node.incrementDependencies();
}
}
public void incrementDependencies(){ dependencies++;}
public void decrementDependencies(){ dependencies--;}
public String getName() { return name;}
public ArrayList<Project> getChildren() {return children;}
public int getNumberDependencies() { return dependencies;}
}