Graph

Question 1

Course Schedule

Answer 1

class Solution {
    public boolean canFinish(int numCourses, int[][] edges) {
      if (numCourses == 0 || edges.length == 0) return true;

      //convert the graph into indegree and out degree
      int indegree[] = new int[numCourses];
      for (int i = 0;i q = new LinkedList<>();
      for (int i = 0;i

Question 2

Course Schedule 2

Answer 2

class Solution {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // check base conditions
        if (numCourses == 0) return null;
        // loop through the courses and add the indegrees
        int[] indegree = new int[numCourses];
        int[] order = new int[numCourses];
        int index = 0;

        // add vertex to the indegree
        for (int[] p : prerequisites){
            int source = p[0];
            indegree[source]++;
        }

        // add to the queue which is 0
        Queue q = new LinkedList<>();
        for (int i=0;i

Question 3

Graph Valid Tree

Answer 3

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        // initialize adjacency list
        List> adjList = new ArrayList>(n);

        // initialize vertices
        for (int i = 0; i < n; i++)
            adjList.add(i, new ArrayList());

    // add edges    
    for (int i = 0; i < edges.length; i++) {
        int u = edges[i][0], v = edges[i][1];
        adjList.get(u).add(v);
        adjList.get(v).add(u);
    }

    boolean[] visited = new boolean[n];

        // make sure there's no cycle
        if (hasCycle(adjList, 0, visited, -1))
            return false;

        // make sure all vertices are connected
        for (int i = 0; i < n; i++) {
            if (!visited[i]) 
                return false;
        }

    return true;
}

    // check if an undirected graph has cycle started from vertex u
    boolean hasCycle(List> adjList, int u, boolean[] visited, int parent) {
        visited[u] = true;

    for (int i = 0; i < adjList.get(u).size(); i++) {
        int v = adjList.get(u).get(i);

        if ((visited[v] && parent != v) || (!visited[v] && hasCycle(adjList, v, visited, u)))
            return true;
    }

    return false;
} }

Question 4

Graph Valid Tree - Union Find

Answer 4

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (n <= 1) {
            return true;
        }
        HashMap map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(i, i);
        }
        for (int[] edge : edges) {
            int fa_x = find(edge[0], map);
            int fa_y = find(edge[1], map);
            if (fa_x == fa_y) {
                return false;
            }
            if (fa_x != fa_y) {
                map.put(fa_x, fa_y);
                n--;
            }
        }
        if (n == 1) {
            return true;
        }
        return false;
    }
    private int find(int x, HashMap map) {
        int father = map.get(x);
        while (father != map.get(father)) {
            father = map.get(father);
        }
        //compressed:
        while (x != map.get(x)) {
            int temp = map.get(x);
            map.put(x, father);
            x = temp;
        }
        //end
        return father;
    }
}

Question 5

Clone Graph

Answer 5

public class Solution {
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        Map map = new HashMap<>();
        return clone(node, map);
    }

    public UndirectedGraphNode clone(UndirectedGraphNode node, Map map){
        if (node == null) return null;
        if (map.containsKey(node.label)) return map.get(node.label);
        UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
        map.put(clone.label, clone);
        for (UndirectedGraphNode neighbor : node.neighbors)
            clone.neighbors.add(clone(neighbor, map));
        return clone;
    }
}