My Java Solution: Strongly Connected Components


  • 1
    V

    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) {
    
        Integer[][] graph = createGraph(size, 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);
        }
        out.add(v);
      }
    
      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>());
        }
        for (int[] pair: adjs) {
          int v = pair[0];
          graph.get(v).add(pair[1]);
        }
    
        for (Integer v: graph.keySet()) {
          List<Integer> vlist = graph.get(v);
          Integer[] varray = new Integer[vlist.size()];
          res[v] = vlist.toArray(varray);
        }
        return res;
      }
    }

Log in to reply
 

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