JetBrains Academy: Topological sort in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki
DAG checker:
Determine if the given graph is a DAG.
Input: The first line contains two numbers n and m – the number of nodes in the graph and the number of edges. The next m lines describe edges by their starting point and their endpoint in the graph.
Output: YES, if the given graph is DAG, and NO, if it is not.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int nodes = scanner.nextInt();
int edges = scanner.nextInt();
Graph graph = new Graph(nodes);
for (int i = 0; i < edges; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
graph.addEdge(a, b);
}
String answer = graph.isDAG() ? "YES" : "NO";
System.out.println(answer);
}
}
class Graph {
private final int size;
private final List<Integer>[] adjList;
private List<Integer> topSort;
private boolean[] visited;
public Graph(int n) {
this.size = n;
adjList = new ArrayList[n + 1];
topSort = new ArrayList<>();
visited = new boolean[n + 1];
for (int i = 1; i <= size; i++) {
adjList[i] = new ArrayList<>();
}
}
public int getSize() {
return this.size;
}
public void addEdge(int a, int b) {
adjList[a].add(b);
}
private void dfs(int node) {
visited[node] = true;
for (Integer next : adjList[node]) {
if (!visited[next]) {
dfs(next);
}
}
topSort.add(node);
}
public List<Integer> topologicalSort() {
for (int i = 1; i <= size; i++) {
visited[i] = false;
}
topSort.clear();
for (int i = 1; i <= size; i++) {
if (!visited[i]) {
dfs(i);
}
}
Collections.reverse(topSort);
return topSort;
}
public boolean isDAG() {
topologicalSort();
for (int i = 0; i < size; i++) {
for (int j = 0; j <= i; j++) {
if (adjList[topSort.get(i)].contains(topSort.get(j))) {
return false;
}
}
}
return true;
}
}Variables and constraints:
You are given several variables. There are a few constraints for those variables. Determine if the constraints conflict with each other. In case they don’t, print the number of variables that can take the smallest values.
Input: The first line contains two numbers n – the number of variables, and m - the number of constraints. Next n lines have names of variables in Latin. The length of a variable name is less than 11. The next m lines describe constraints: {name1} < {name2} or {name1} > {name2}.
Output: NO, if constraints contradict each other. Otherwise print the number of variables that can take the smallest values.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] params = scanner.nextLine().split("\\s+");
int variables = Integer.parseInt(params[0]);
int constraints = Integer.parseInt(params[1]);
Graph<String> graph = new Graph<>(variables);
for (int i = 0; i < variables; i++) {
graph.addNode(scanner.nextLine());
}
for (int i = 0; i < constraints; i++) {
String inputLine = scanner.nextLine();
InputUtils.executeLine(inputLine, graph);
}
System.out.println(graph.countMinimums());
}
}class InputUtils {
public static void executeLine(String inputLine, Graph<String> graph) {
String sign;
String[] array = inputLine.split("<");
if (array.length == 2) {
sign = "<";
} else {
array = array[0].split(">");
sign = ">";
}
String a = array[0];
String b = array[1];
Constraint.run(a, sign, b, graph);
}
}enum Constraint {
GREATER_THAN(">") {
@Override
public void apply(String a, String b, Graph<String> graph) {
graph.addEdge(b, a);
}
}, LESS_THAN("<") {
@Override
public void apply(String a, String b, Graph<String> graph) {
graph.addEdge(a, b);
}
};
private String sign;
Constraint(String sign) {
this.sign = sign;
}
public static void run(String a, String sign, String b, Graph<String> graph) {
for (Constraint constraint : Constraint.values()) {
if (constraint.sign.equals(sign)) {
Constraint lessOrGreater = constraint;
lessOrGreater.apply(a, b, graph);
}
}
}
public abstract void apply(String a, String b, Graph<String> graph);
}class Graph<E> {
private final int size;
private final List<E>[] adjList;
private final List<E> topSort;
private final boolean[] visited;
private final List<E> nodes;
private final List<E> minimums;
public Graph(int n) {
this.size = n;
adjList = new ArrayList[n + 1];
topSort = new ArrayList<>();
visited = new boolean[n + 1];
nodes = new ArrayList<>();
minimums = new ArrayList<>();
for (int i = 0; i < size; i++) {
adjList[i] = new ArrayList<>();
}
}
public int getSize() {
return this.size;
}
public List<E> getPossibleMinimums() {
return minimums;
}
public int countMinimums() {
if (this.isDAG()) {
return this.getPossibleMinimums().size();
} else {
throw new RuntimeException("NO");
}
}
public void addNode(E node) {
nodes.add(node);
minimums.add(node);
}
public void addEdge(E a, E b) {
if (!nodes.contains(a)) {
addNode(a);
}
if (!nodes.contains(b)) {
addNode(b);
}
int indexA = nodes.indexOf(a);
adjList[indexA].add(b);
minimums.remove(b);
}
private void dfs(int node) {
visited[node] = true;
for (E next : adjList[node]) {
if (!visited[nodes.indexOf(next)]) {
dfs(nodes.indexOf(next));
}
}
topSort.add(nodes.get(node));
}
public List<E> topologicalSort() {
for (int i = 0; i < size; i++) {
visited[i] = false;
}
topSort.clear();
for (int i = 0; i < size; i++) {
if (!visited[i]) {
dfs(i);
}
}
Collections.reverse(topSort);
return topSort;
}
public boolean isDAG() {
topologicalSort();
for (int i = 0; i < size; i++) {
for (int j = 0; j <= i; j++) {
final E node = topSort.get(i);
int index = nodes.indexOf(node);
if (adjList[index].contains(topSort.get(j))) {
return false;
}
}
}
return true;
}
}Alphabet:
There is a made-up language. Determine the alphabetic order of its letters using lexicographically ordered words from the language. It is guaranteed that such order exists and is unambiguous.
Input: Number n in the first line is the number of words from the language, ordered lexicographically. Next n lines contain those words. The length of each word is no greater than 20 characters.
Output: Print the alphabet of the language without spaces. There's only one correct output.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int lines = Integer.parseInt(scanner.nextLine());
String[] orderedWords = new String[lines];
for (int i = 0; i < lines; i++) {
orderedWords[i] = scanner.nextLine();
}
String alphabet = GraphUtils.createAlphabetFrom(orderedWords);
System.out.println(alphabet);
}
}class GraphUtils {
public static String createAlphabetFrom(String... words) {
Graph<Character> alphabet = new Graph<>(20);
checkFirstLetter(words, alphabet);
checkLetters(words, alphabet);
alphabet.topologicalSort();
return alphabet.toString();
}
private static void checkLetters(String[] words, Graph<Character> alphabet) {
for (int i = 0; i < words.length - 1; i++) {
String s = words[i];
String t = words[i + 1];
int minLength = Math.min(s.length(), t.length());
for (int j = 1; j < minLength; j++) {
if (s.charAt(j - 1) == t.charAt(j - 1) && s.charAt(j) != t.charAt(j)) {
char a = s.charAt(j);
char b = t.charAt(j);
alphabet.addEdge(a, b);
break;
}
}
}
}
private static void checkFirstLetter(String[] words, Graph<Character> alphabet) {
for (int i = 0; i < words.length - 1; i++) {
String s = words[i];
String t = words[i + 1];
if (s.charAt(0) != t.charAt(0)) {
char a = s.charAt(0);
char b = t.charAt(0);
alphabet.addEdge(a, b);
}
}
}
}class Graph<E> {
private final int capacity;
private final List<E>[] adjList;
private final List<E> topSort;
private final boolean[] visited;
private final List<E> nodes;
private final List<E> minimums;
public Graph(int n) {
this.capacity = n;
adjList = new ArrayList[n + 1];
topSort = new ArrayList<>();
visited = new boolean[n + 1];
nodes = new ArrayList<>();
minimums = new ArrayList<>();
for (int i = 0; i < capacity; i++) {
adjList[i] = new ArrayList<>();
}
}
public int getCapacity() {
return this.capacity;
}
public List<E> getPossibleMinimums() {
return minimums;
}
public int countMinimums() {
if (this.isDAG()) {
return this.getPossibleMinimums().size();
} else {
throw new RuntimeException("NO");
}
}
public void addNode(E node) {
nodes.add(node);
minimums.add(node);
}
public void addEdge(E a, E b) {
if (!nodes.contains(a)) {
addNode(a);
}
if (!nodes.contains(b)) {
addNode(b);
}
int indexA = nodes.indexOf(a);
adjList[indexA].add(b);
minimums.remove(b);
}
private void dfs(int node) {
visited[node] = true;
for (E next : adjList[node]) {
if (!visited[nodes.indexOf(next)]) {
dfs(nodes.indexOf(next));
}
}
topSort.add(nodes.get(node));
}
public List<E> topologicalSort() {
for (int i = 0; i < nodes.size(); i++) {
visited[i] = false;
}
topSort.clear();
for (int i = 0; i < nodes.size(); i++) {
if (!visited[i]) {
dfs(i);
}
}
Collections.reverse(topSort);
return topSort;
}
public boolean isDAG() {
topologicalSort();
for (int i = 0; i < capacity; i++) {
for (int j = 0; j <= i; j++) {
final E node = topSort.get(i);
int index = nodes.indexOf(node);
if (adjList[index].contains(topSort.get(j))) {
return false;
}
}
}
return true;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (E elem : nodes) {
sb.append(elem);
}
return sb.toString();
}
}