Skip to content

Instantly share code, notes, and snippets.

@jknair0
Last active May 21, 2022 10:47
Show Gist options
  • Save jknair0/917be0d92212b72ec44176b2760015ed to your computer and use it in GitHub Desktop.
Save jknair0/917be0d92212b72ec44176b2760015ed to your computer and use it in GitHub Desktop.
// https://www.cs.cmu.edu/~15451-f18/lectures/lec19-DFS-strong-components.pdf
import java.util.*;
class Graph {
ArrayList<Integer>[] graph;
public Graph(int n) {
graph = new ArrayList[n];
for (int i = 0; i< n ;i ++) {
graph[i] = new ArrayList<Integer>();
}
}
public void addEdge(int i, int j) {
graph[i].add(j);
}
public ArrayList<Integer> getNeiNodes(int node) {
return graph[node];
}
public void addAll(int[][] edges) {
for (int[] edge: edges) {
addEdge(edge[0], edge[1]);
}
}
}
class SCC {
static boolean[] visited;
static ArrayList<Integer> result;
public static void main(String[] args) {
int n = 13;
Graph graph = new Graph(n);
graph.addAll(new int[][] {
{0, 1},
{0, 2},
{1, 3},
{1, 4},
{3, 7},
{3, 8},
{4, 9},
{4, 10},
{0, 4},
{2, 5},
{2, 6},
{5, 11},
{5, 12}
});
visited = new boolean[n];
result = new ArrayList<>();
for (int node = 0; node < n; node++) {
if (!visited[node]) topSort(graph, 0);
}
System.out.println(result);
}
public static void topSort(Graph graph, int node) {
if(visited[node]) {
return;
}
visited[node] = true;
for (int n: graph.getNeiNodes(node)) {
topSort(graph, n);
}
result.add(node);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment