Created
April 7, 2020 10:12
-
-
Save gordinmitya/15b1105ed14ebd13f9804edb30b5c865 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
public class TopologicalSort { | |
public static final int WHITE = 0; | |
public static final int GRAY = 1; | |
public static final int BLACK = 2; | |
private static void dfs(int v, List<List<Integer>> edges, int[] colors, List<Integer> queue) { | |
colors[v] = GRAY; | |
List<Integer> list = edges.get(v); | |
for (int to : list) { | |
if (colors[to] == GRAY) | |
throw new RuntimeException(String.format("Cycle from %d to %d!", v, to)); | |
if (colors[to] == WHITE) | |
dfs(to, edges, colors, queue); | |
} | |
colors[v] = BLACK; | |
queue.add(v); | |
} | |
private static List<Integer> topoSort(List<List<Integer>> edges, int N) { | |
List<Integer> queue = new ArrayList<>(); | |
int[] colors = new int[N]; // all white | |
for (int i = 0; i < colors.length; i++) { | |
if (colors[i] == WHITE) | |
dfs(i, edges, colors, queue); | |
} | |
return queue; | |
} | |
public static void main(String[] args) { | |
Scanner scanner = new Scanner(System.in); | |
int n = scanner.nextInt(); | |
int e = scanner.nextInt(); | |
List<List<Integer>> edges = new ArrayList<>(); | |
for (int i = 0; i < n; ++i) | |
edges.add(new ArrayList<>()); | |
for (int i = 0; i < e; ++i) { | |
int from = scanner.nextInt() - 1; | |
int to = scanner.nextInt() - 1; | |
edges.get(from).add(to); | |
} | |
List<Integer> result = topoSort(edges, n); | |
for (int i = result.size() - 1; i >= 0; i--) { | |
System.out.format("%d ", result.get(i) + 1); | |
} | |
} | |
} | |
/* | |
n e | |
edges… | |
5 5 | |
1 2 | |
2 3 | |
1 3 | |
4 3 | |
4 5 | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment