125 lines
2.9 KiB
Java
125 lines
2.9 KiB
Java
package chelper;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.Deque;
|
|
import java.util.HashMap;
|
|
import java.util.HashSet;
|
|
import java.util.LinkedList;
|
|
import java.util.List;
|
|
import java.util.Map;
|
|
import java.util.Objects;
|
|
import java.util.Set;
|
|
import java.util.TreeSet;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.SimpleSavingChelperSolution;
|
|
|
|
|
|
public class C extends SimpleSavingChelperSolution {
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
class Project implements Comparable<Project> {
|
|
|
|
final String name;
|
|
final int version;
|
|
|
|
final List<Project> dependencies = new ArrayList<>();
|
|
|
|
public Project(String name, int version) {
|
|
this.name = name;
|
|
this.version = version;
|
|
}
|
|
|
|
@Override
|
|
public int compareTo(Project o) {
|
|
if (!name.equals(o.name)) {
|
|
return name.compareTo(o.name);
|
|
}
|
|
|
|
return -Integer.compare(version, o.version);
|
|
}
|
|
|
|
@Override
|
|
public boolean equals(Object o) {
|
|
if (this == o) return true;
|
|
if (o == null || getClass() != o.getClass()) return false;
|
|
Project project = (Project) o;
|
|
return version == project.version &&
|
|
Objects.equals(name, project.name);
|
|
}
|
|
|
|
@Override
|
|
public int hashCode() {
|
|
return Objects.hash(name, version);
|
|
}
|
|
|
|
@Override
|
|
public String toString() {
|
|
return String.format("%s %d", name, version);
|
|
}
|
|
}
|
|
|
|
Map<String, Map<Integer, Project>> allProjects = new HashMap<>();
|
|
|
|
Project getProject(String name, int version) {
|
|
allProjects.putIfAbsent(name, new HashMap<>());
|
|
allProjects.get(name).putIfAbsent(version, new Project(name, version));
|
|
|
|
return allProjects.get(name).get(version);
|
|
}
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
int n = in.nextInt();
|
|
|
|
List<Project> projects = new ArrayList<>();
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
Project project = getProject(in.nextString(), in.nextInt());
|
|
|
|
projects.add(project);
|
|
|
|
int depCount = in.nextInt();
|
|
for (int j = 0; j < depCount; j++) {
|
|
Project depProject = getProject(in.nextString(), in.nextInt());
|
|
project.dependencies.add(depProject);
|
|
}
|
|
}
|
|
|
|
Set<Project> dependencies = new TreeSet<>();
|
|
Set<String> dependencyNames = new TreeSet<>();
|
|
|
|
Set<Project> neighbors = new TreeSet<>();
|
|
|
|
neighbors.add(projects.get(0));
|
|
|
|
while (!neighbors.isEmpty()) {
|
|
Set<Project> nextNeighbors = new TreeSet<>();
|
|
|
|
for (Project neighbor : neighbors) {
|
|
if (dependencyNames.contains(neighbor.name)) {
|
|
continue;
|
|
}
|
|
|
|
dependencyNames.add(neighbor.name);
|
|
dependencies.add(neighbor);
|
|
|
|
nextNeighbors.addAll(neighbor.dependencies);
|
|
}
|
|
|
|
neighbors = nextNeighbors;
|
|
}
|
|
|
|
dependencies.remove(projects.get(0));
|
|
|
|
out.println(dependencies.size());
|
|
for (Project dependency : dependencies) {
|
|
out.println(dependency);
|
|
}
|
|
}
|
|
}
|