My Java Solution: Strongly Connected Components

• The idea is simple - we try to fing all SCC. if node size more then 1 - we have a loop.

``````public class Solution {

public boolean canFinish(int size, int[][] adjs) {

boolean[] visited = new boolean[size];
List<Integer> vlist = new ArrayList<>();

for (int v = 0; v < graph.length; v++) {
if (!visited[v]) {
dfs(graph, visited, v, vlist);
}
}

visited = new boolean[size];

for (Integer v : vlist) {// reverse traversal
List<Integer> wlist = new ArrayList<>();
dfs(graph, visited, v, wlist);
if (wlist.size() > 1) {
return false;
}
}

return true;
}

void dfs(Integer[][] graph, boolean[] visited, int v, List<Integer> out) {
visited[v] = true;

for (Integer w : graph[v]) {
if (visited[w]) break;
dfs(graph, visited, w, out);
}
}

Integer[][] createGraph(int size, int[][] adjs) {
Integer[][] res = new Integer[size][];

Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < size; i++) {
graph.put(i, new ArrayList<Integer>());
}
int v = pair[0];
}

for (Integer v: graph.keySet()) {
List<Integer> vlist = graph.get(v);
Integer[] varray = new Integer[vlist.size()];
res[v] = vlist.toArray(varray);
}
return res;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.