Undirected graph: when dfs, must skip prev node!

DFS template:

private boolean hasCycle (int prev, int node, Map<Integer, List<Integer>> graph, int[] status) {
    status[node] = 1;
    if (graph.get(node) == null) {
        status[node] = 2;
        return false;
    }
    for (int nei : graph.get(node)) {
        if (status[nei] == 2 || nei == prev) continue;
        if (status[nei] == 1) return true;
        if (hasCycle(node, nei, graph, status)) return true;
    }
    status[node] = 2;
    return false;
}

BFS template:

private boolean hasCycle(Map<Integer, List<Integer>> graph, int[] status) {
    Queue<Integer> queue = new LinkedList<Integer>();
    queue.add(0);
    status[0] = 1;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int currt = queue.poll();
            if (graph.get(currt) == null) {
                status[currt] = 2;
                continue;
            } 
            for (int nei : graph.get(currt)) {
                if (status[nei] == 1) return true;
                if (status[nei] == 2) continue;
                status[nei] = 1;
                queue.add(nei);
            }
            status[currt] = 2;
        }
    }
    return false;
}

1. Graph Valid Tree

detect cycle + detect the seperated components

要想形成一个valid tree的话，得满足上面两个条件。

detect cycle:

graph一般都有两种做法：dfs & bfs。很类似，不同于directed graph的是，需要记录访问的三种状态。

status[]: 0 -> unvisited, 1 -> visiting, 2 -> done。

因为给的是2d array，要转换成adjacent list。

detect connected components:

遍历status array，如果有0的话，就代表还有点没有被访问过，则是有more than one connected components。

DFS

注意，dfs的时候，需要检测当前要遍历的neighbor是不是predecessor，即是不是从那个vertice来的。是的话，要跳过。因为predessor的状态一定是1，还没访问完呢。

class Solution {
    public boolean validTree(int n, int[][] edges) {
        Map<Integer, List<Integer>> graph = convertToGraph(edges);
        int[] status = new int[n];
        if (hasCycle(-1, 0, graph, status)) return false;
        if (hasSeperatedComponent(status)) return false;
        return true;
    }

    private Map<Integer, List<Integer>> convertToGraph (int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            if (!graph.containsKey(edge[0])) graph.put(edge[0], new LinkedList<Integer>());
            if (!graph.containsKey(edge[1])) graph.put(edge[1], new LinkedList<Integer>());
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        return graph;
    }

    private boolean hasCycle (int prev, int node, Map<Integer, List<Integer>> graph, int[] status) {
        status[node] = 1;
        if (graph.get(node) == null) {
            status[node] = 2;
            return false;
        }
        for (int nei : graph.get(node)) {
            if (status[nei] == 2 || nei == prev) continue;
            if (status[nei] == 1) return true;
            if (hasCycle(node, nei, graph, status)) return true;
        }
        status[node] = 2;
        return false;
    }

    private boolean hasSeperatedComponent(int[] status) {
        for (int s : status) {
            if (s == 0) return true;
        }
        return false;
    }
}

BFS

大体是一样的，唯一需要改的Method是hasCycle()。

用queue遍历vertice。

class Solution {
    public boolean validTree(int n, int[][] edges) {
        Map<Integer, List<Integer>> graph = convertToGraph(edges);
        int[] status = new int[n];
        //bfs
        if (hasCycle(graph, status)) return false;
        if (hasSeperatedComponent(status)) return false;
        return true;
    }

    private Map<Integer, List<Integer>> convertToGraph (int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            if (!graph.containsKey(edge[0])) graph.put(edge[0], new LinkedList<Integer>());
            if (!graph.containsKey(edge[1])) graph.put(edge[1], new LinkedList<Integer>());
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        return graph;
    }

    //bfs
    private boolean hasCycle(Map<Integer, List<Integer>> graph, int[] status) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(0);
        status[0] = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int currt = queue.poll();
                if (graph.get(currt) == null) {
                    status[currt] = 2;
                    continue;
                } 
                for (int nei : graph.get(currt)) {
                    if (status[nei] == 1) return true;
                    if (status[nei] == 2) continue;
                    status[nei] = 1;
                    queue.add(nei);
                }
                status[currt] = 2;
            }
        }
        return false;
    }

    private boolean hasSeperatedComponent(int[] status) {
        for (int s : status) {
            if (s == 0) return true;
        }
        return false;
    }
}

Union find

Union find template, 唯一的变化就是，为了要判断有多少个component，在union find class里面加了一个count来记录component的个数

class Solution {
    public boolean validTree(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges) {
            if (!uf.union(edge[0], edge[1])) return false;
        }
        return uf.count == 1;
    }

    //union find + path compression & union by rank
    class UnionFind {
        int[] parent;
        int[] size;
        int count;

        public UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
            count = n;
        }

        private boolean union(int node1, int node2) {
            int root1 = find(node1);
            int root2 = find(node2);
            if (root1 == root2) return false;//connected, no need to union
            //link root of smaller tree to the root of larger tree
            if (size[root1] < size[root2]) {
                parent[root1] = root2;
                size[root2] += size[root1];
            } else {
                parent[root2] = root1;
                size[root1] += size[root2];
            }
            count--;
            return true;
        }

        //find the root + path compression
        //path compression: flatten the tree. link all nodes directly to the root
        //to improve the find method running time.
        private int find(int node) {
            if (parent[node] != node) {
                parent[node] = find(parent[node]);
            }
            return parent[node];
        }
    }
}

2. Clone Graph

dfs: add the new cloned node into map even before putting into map, to avoid stack overflow

stack overflow example: 1 -> 2, 2 -> 1

public class Solution {

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return node;
        Map<Integer, UndirectedGraphNode> map = new HashMap<>();
        return clone(map, node);
    }

    private UndirectedGraphNode clone (Map<Integer, UndirectedGraphNode> map, UndirectedGraphNode node) {
        if (map.containsKey(node.label)) return map.get(node.label);
        UndirectedGraphNode clonedNode = new UndirectedGraphNode(node.label);
        map.put(node.label, clonedNode);//put it before dfs to avoid stack overflow
        for (UndirectedGraphNode nei : node.neighbors) {
            clonedNode.neighbors.add(clone(map, nei));
        }
        return clonedNode;
    }
}

bfs

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) return node;
    Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
    Map<Integer, UndirectedGraphNode> newNodes = new HashMap<>();
    queue.add(node);
    UndirectedGraphNode newHead = new UndirectedGraphNode(node.label);
    newNodes.put(node.label, newHead);
    while (!queue.isEmpty()) {
        UndirectedGraphNode currt = queue.poll();
        UndirectedGraphNode newCurrt = newNodes.get(currt.label);
        for (UndirectedGraphNode nei : currt.neighbors) {
            if (!newNodes.containsKey(nei.label)) {
                UndirectedGraphNode newNode = new UndirectedGraphNode(nei.label);
                newNodes.put(nei.label, newNode);
                queue.add(nei);
            }
            newCurrt.neighbors.add(newNodes.get(nei.label));
        }
    }
    return newHead;
}

clone node + map: (old node --> new node) + connect node

具体的分为三个步骤。

找到所有的Node。这里有多种做法，可以bfs, dfs。
hash map: old node -- > new node。这里主要是为了后面可以connect node。因为new nodes之间要建立关系。所以在找neighbor的时候，需要用map找到相应的new node，再连接。
连接new nodes，以达到deep clone的效果

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return node;
        //clone node
        Set<UndirectedGraphNode> set = new HashSet<UndirectedGraphNode>();
        set.add(node);
        dfs(set, node);

        //map node
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        for (UndirectedGraphNode n: set) {
            map.put(n, new UndirectedGraphNode(n.label));
        }

        //connect node
        for (UndirectedGraphNode n: set) {
            //用new node
            UndirectedGraphNode newNode = map.get(n);
            for (UndirectedGraphNode neighbor: n.neighbors) {
                //连接new node
                UndirectedGraphNode newNeighbor = map.get(neighbor);
                newNode.neighbors.add(newNeighbor);
            }
        }

        return map.get(node);
    }

    private void dfs(Set<UndirectedGraphNode> set, UndirectedGraphNode node) {
        for (UndirectedGraphNode n: node.neighbors) {
            if(set.contains(n)) continue;
            set.add(n);
            dfs(set, n);
        }
    }
}

3. Copy List with Random Pointer

可以看做一个特殊的graph。

O(n) space + O(n) time: map old node --> new node + setup random pointers

O(1) space + O(n) time: insert new node after old node + restore the original list and extract the duplicated nodes.

第一种做法很类似上面的，也是要map一下新旧node，建立Random pointer的时候利用map来确定node。简单，但是空间可以优化。

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return head;
        //map nodes
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode dummy = head;
        while (head != null) {
            map.put(head, new RandomListNode(head.label));
            head = head.next;
        }

        //setup next and random pointers
        head = dummy;
        while (head != null) {
            map.get(head).next = map.get(head.next);
            map.get(head).random = map.get(head.random);
            head = head.next;
        }
        return map.get(dummy);
    }
}

在每个节点后面插入新节点，最后再拆出来

4. Minimum Height Trees

setup adjacent list + 剥洋葱一样，把每一层的leaf nodes去除，直到剩下一个或者两个node + int[] degree

基本就是层层剥削，直到中间的点。我们知道如果要找Min height的话，root最好是中间的点。拓展到graph的话，也是一样的道理。先把外围的leaf nodes清除了。用了int[]去数每个点的degree，当degree == 1的时候，就说明这个点只和一个点连着，是leaf node。

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        int[] degrees = new int[n];
        Map<Integer, List<Integer>> graph = convertToGraph(edges, degrees);
        List<Integer> leaves = getLeaves(degrees);
        return removeLeaves(n, graph, leaves, degrees);
    }

    private Map<Integer, List<Integer>> convertToGraph (int[][] edges, int[] degrees) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            if (!graph.containsKey(edge[0])) graph.put(edge[0], new LinkedList<Integer>());
            if (!graph.containsKey(edge[1])) graph.put(edge[1], new LinkedList<Integer>());
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
            degrees[edge[0]]++;
            degrees[edge[1]]++;
        }
        return graph;
    }

    private List<Integer> removeLeaves(int n, Map<Integer, List<Integer>> graph, List<Integer> leaves, int[] degrees) {
        while (n > 2) {
            int size = leaves.size();
            n -= size;
            for (int i = 0; i < size; i++) {
                int currt = leaves.remove(0);
                for (int nei : graph.get(currt)) {
                    degrees[nei]--;
                    if (degrees[nei] == 1) leaves.add(nei);
                } 
            }
        }
        return leaves;
    }

    private List<Integer> getLeaves(int[] degrees) {
        List<Integer> roots = new LinkedList<Integer>();
        for (int i = 0; i < degrees.length; i++) {
            if (degrees[i] <= 1) roots.add(i);
        }
        return roots;
    }
}

5. Number of Connected Components in an Undirected Graph

BFS, status array, pick unvisited node

TODO: Union find

BFS version

class Solution {
    public int countComponents(int n, int[][] edges) {
        //bfs + pick unvisited node
        //construct graph
        ArrayList[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        for (int[] edge: edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        int[] status = new int[n];
        int num = 0;
        int start = pickNode(status);
        while (start != -1) {
            //bfs 
            num++;
            Queue<Integer> queue = new LinkedList<Integer>();
            queue.add(start);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int curr = queue.poll();
                    status[curr] = 1;
                    ArrayList<Integer> neighbors = graph[curr];
                    for (int nei: neighbors) {
                        if (status[nei] != 1) {
                            queue.add(nei);
                            status[nei] = 1;
                        }
                    }
                }
            }
            start = pickNode(status);
        }
        return num;
    }

    private int pickNode(int[] status) {
        for (int i = 0; i < status.length; i++) {
            if (status[i] == 0) return i;
        }
        return -1;
    }
}

Union Find

undirected graph