[Function add]

Seanforfun · Seanforfun · commit 8390810e5730 · 2019-03-26T16:59:36.000-04:00
1. Add leetcode solutions with tag graph.
diff --git a/leetcode/684. Redundant Connection.md b/leetcode/684. Redundant Connection.md
@@ -0,0 +1,75 @@
+## 684. Redundant Connection
+
+### Question:
+ In this problem, a tree is an undirected graph that is connected and has no cycles.
+
+The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
+
+The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.
+
+Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.
+
+```
+Example 1:
+
+Input: [[1,2], [1,3], [2,3]]
+Output: [2,3]
+Explanation: The given undirected graph will be like this:
+  1
+ / \
+2 - 3
+
+Example 2:
+
+Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
+Output: [1,4]
+Explanation: The given undirected graph will be like this:
+5 - 1 - 2
+    |   |
+    4 - 3
+```
+
+Note:
+* The size of the input 2D-array will be between 3 and 1000.
+* Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.
+
+### Solution:
+* Method 1: dfs
+    * how to find a cycle?
+        * before we add current path (u, v) to the graph, we can already find the path from u to v, so after adding current edge, there exists a cycle.
+    ```Java
+    class Solution {
+        private Map<Integer, List<Integer>> graph;
+        public int[] findRedundantConnection(int[][] edges) {
+            graph = new HashMap<>();
+            for(int[] edge : edges){
+                Set<Integer> visited = new HashSet<>();
+                if(hasPath(edge[0], edge[1], visited))
+                    return edge;
+                List<Integer> temp = graph.containsKey(edge[0]) ? graph.get(edge[0]): new ArrayList<>();
+                temp.add(edge[1]);
+                graph.put(edge[0], temp);
+                temp = graph.containsKey(edge[1]) ? graph.get(edge[1]): new ArrayList<>();
+                temp.add(edge[0]);
+                graph.put(edge[1], temp);
+            }
+            return new int[]{-1, -1};
+        }
+        private boolean hasPath(int u, int v, Set<Integer> visited){
+            if(u == v) return true;
+            visited.add(u);
+            if(!graph.containsKey(u) || !graph.containsKey(v)) return false;
+            List<Integer> nexts = graph.get(u);
+            for(Integer next : nexts){
+                if(visited.contains(next)) continue;
+                if(hasPath(next, v, visited)) return true;
+            }
+            return false;
+        }
+    }
+    ```
+
+* Method 2: Union find set to be added
+
+### Reference
+1. [花花酱 LeetCode 684. Redundant Connection](http://zxi.mytechroad.com/blog/tree/leetcode-684-redundant-connection/)
diff --git a/leetcode/785. Is Graph Bipartite.md b/leetcode/785. Is Graph Bipartite.md
@@ -0,0 +1,94 @@
+## 785. Is Graph Bipartite?
+
+### Question:
+Given an undirected graph, return true if and only if it is bipartite.
+
+Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.
+
+The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists.  Each node is an integer between 0 and graph.length - 1.  There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.
+
+```
+Example 1:
+Input: [[1,3], [0,2], [1,3], [0,2]]
+Output: true
+Explanation: 
+The graph looks like this:
+0----1
+|    |
+|    |
+3----2
+We can divide the vertices into two groups: {0, 2} and {1, 3}.
+
+Example 2:
+Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
+Output: false
+Explanation: 
+The graph looks like this:
+0----1
+| \  |
+|  \ |
+3----2
+We cannot find a way to divide the set of nodes into two independent subsets.
+```
+
+Note:
+* graph will have length in range [1, 100].
+* graph[i] will contain integers in range [0, graph.length - 1].
+* graph[i] will not contain i or duplicate values.
+* The graph is undirected: if any element j is in graph[i], then i will be in graph[j].
+
+### Solution:
+* Method 1: dfs + bopartite
+    ```Java
+    class Solution {
+        private int[][] g;
+        private int[] visited;
+        public boolean isBipartite(int[][] graph) {
+            g = graph;
+            visited = new int[graph.length];        
+            for(int i = 0; i < graph.length; i++){
+                if(visited[i] == 0){
+                    if(!dfs(i, 1))  return false;
+                }
+            }
+            return true;
+        }
+        private boolean dfs(int node, int color){
+            if(visited[node] == -color) return false;
+            else if(visited[node] == color) return true;
+            visited[node] = color;
+            int[] neighbours = g[node];
+            for(Integer neighbour : neighbours){
+                if(!dfs(neighbour, -color)) return false;
+            }
+            return true;
+        }
+    }
+    ```
+
+* Method 2: bfs
+    ```Java
+    class Solution {
+        public boolean isBipartite(int[][] graph) {
+            int[] visited = new int[graph.length];
+            Queue<Integer> queue = new LinkedList<>();
+            for(int i = 0; i < graph.length; i++){
+                if(visited[i] == 0){
+                    visited[i] = 1;
+                    queue.offer(i);
+                    while(!queue.isEmpty()){
+                        int cur = queue.poll();
+                        for(Integer next : graph[cur]){
+                            if(visited[next] == visited[cur]) return false;
+                            else if(visited[next] == 0){
+                                visited[next] = -visited[cur];
+                                queue.offer(next);
+                            }
+                        }
+                    }
+                }
+            }
+            return true;
+        }
+    }
+    ```
