2508. Add Edges to Make Degrees of All Nodes Even Hard

1/**
2 * [2508] Add Edges to Make Degrees of All Nodes Even
3 *
4 * There is an undirected graph consisting of n nodes numbered from 1 to n. You are given the integer n and a 2D array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi. The graph can be disconnected.
5 * You can add at most two additional edges (possibly none) to this graph so that there are no repeated edges and no self-loops.
6 * Return true if it is possible to make the degree of each node in the graph even, otherwise return false.
7 * The degree of a node is the number of edges connected to it.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2022/10/26/agraphdrawio.png" style="width: 500px; height: 190px;" />
11 * Input: n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]
12 * Output: true
13 * Explanation: The above diagram shows a valid way of adding an edge.
14 * Every node in the resulting graph is connected to an even number of edges.
15 * 
16 * Example 2:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2022/10/26/aagraphdrawio.png" style="width: 400px; height: 120px;" />
18 * Input: n = 4, edges = [[1,2],[3,4]]
19 * Output: true
20 * Explanation: The above diagram shows a valid way of adding two edges.
21 * Example 3:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2022/10/26/aaagraphdrawio.png" style="width: 150px; height: 158px;" />
23 * Input: n = 4, edges = [[1,2],[1,3],[1,4]]
24 * Output: false
25 * Explanation: It is not possible to obtain a valid graph with adding at most 2 edges.
26 *  
27 * Constraints:
28 * 
29 * 	3 <= n <= 10^5
30 * 	2 <= edges.length <= 10^5
31 * 	edges[i].length == 2
32 * 	1 <= ai, bi <= n
33 * 	ai != bi
34 * 	There are no repeated edges.
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/add-edges-to-make-degrees-of-all-nodes-even/
40// discuss: https://leetcode.com/problems/add-edges-to-make-degrees-of-all-nodes-even/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn is_possible(n: i32, edges: Vec<Vec<i32>>) -> bool {
46        false
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_2508() {
58    }
59}
60