1042. Flower Planting With No Adjacent Medium

1/**
2 * [1042] Flower Planting With No Adjacent
3 *
4 * You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [xi, yi] describes a bidirectional path between garden xi to garden yi. In each garden, you want to plant one of 4 types of flowers.
5 * All gardens have at most 3 paths coming into or leaving it.
6 * Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.
7 * Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)^th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.
8 *  
9 * Example 1:
10 * 
11 * Input: n = 3, paths = [[1,2],[2,3],[3,1]]
12 * Output: [1,2,3]
13 * Explanation:
14 * Gardens 1 and 2 have different types.
15 * Gardens 2 and 3 have different types.
16 * Gardens 3 and 1 have different types.
17 * Hence, [1,2,3] is a valid answer. Other valid answers include [1,2,4], [1,4,2], and [3,2,1].
18 * 
19 * Example 2:
20 * 
21 * Input: n = 4, paths = [[1,2],[3,4]]
22 * Output: [1,2,1,2]
23 * 
24 * Example 3:
25 * 
26 * Input: n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
27 * Output: [1,2,3,4]
28 * 
29 *  
30 * Constraints:
31 * 
32 * 	1 <= n <= 10^4
33 * 	0 <= paths.length <= 2 * 10^4
34 * 	paths[i].length == 2
35 * 	1 <= xi, yi <= n
36 * 	xi != yi
37 * 	Every garden has at most 3 paths coming into or leaving it.
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/flower-planting-with-no-adjacent/
43// discuss: https://leetcode.com/problems/flower-planting-with-no-adjacent/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn garden_no_adj(n: i32, paths: Vec<Vec<i32>>) -> Vec<i32> {
49        vec![]
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_1042() {
61    }
62}
63