785. Is Graph Bipartite? Medium

1/**
2 * [785] Is Graph Bipartite?
3 *
4 * There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:
5 * 
6 * 	There are no self-edges (graph[u] does not contain u).
7 * 	There are no parallel edges (graph[u] does not contain duplicate values).
8 * 	If v is in graph[u], then u is in graph[v] (the graph is undirected).
9 * 	The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.
10 * 
11 * A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.
12 * Return true if and only if it is bipartite.
13 *  
14 * Example 1:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/21/bi2.jpg" style="width: 222px; height: 222px;" />
16 * Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
17 * Output: false
18 * Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.
19 * Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/21/bi1.jpg" style="width: 222px; height: 222px;" />
21 * Input: graph = [[1,3],[0,2],[1,3],[0,2]]
22 * Output: true
23 * Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.
24 *  
25 * Constraints:
26 * 
27 * 	graph.length == n
28 * 	1 <= n <= 100
29 * 	0 <= graph[u].length < n
30 * 	0 <= graph[u][i] <= n - 1
31 * 	graph[u] does not contain u.
32 * 	All the values of graph[u] are unique.
33 * 	If graph[u] contains v, then graph[v] contains u.
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/is-graph-bipartite/
39// discuss: https://leetcode.com/problems/is-graph-bipartite/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn is_bipartite(graph: Vec<Vec<i32>>) -> bool {
45        false
46    }
47}
48
49// submission codes end
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_785() {
57    }
58}
59