Count Components With a Prime Total Value
Updated
Problem statement
You are given an undirected graph with n vertices labeled from 0 to n - 1, where n = values.length. Vertex i has the value values[i]. Each edges[j] = [a, b] joins vertices a and b, and you can move along an edge in either direction.
A connected component is a largest group of vertices in which every vertex can reach every other vertex by following edges. A vertex with no edges is a component by itself. The total of a component is the sum of the values of all its vertices.
Return the number of connected components whose total is a prime number. A prime number is a whole number greater than 1 whose only positive divisors are 1 and itself, so the totals 0 and 1 are not prime.
Function
countPrimeComponents(values: int[], edges: int[][]) → intExamples
Example 1
values = [3,4,1,6,7,2]edges = [[0,1],[1,2],[3,4]]return = 2There are three components. Vertices 0, 1 and 2 have total 3 + 4 + 1 = 8, which is not prime. Vertices 3 and 4 have total 6 + 7 = 13, which is prime. Vertex 5 has no edges, so it is a component by itself with total 2, which is prime. Two components have a prime total.
Example 2
values = [1,0,1,0]edges = [[1,3]]return = 0The components are {0} with total 1, {1, 3} with total 0, and {2} with total 1. Neither 0 nor 1 is prime, so the answer is 0.
Example 3
values = [4,9,6,1,10]edges = [[0,1],[2,3],[1,4]]return = 2No single vertex value here is prime. The component {0, 1, 4} has total 4 + 9 + 10 = 23 and the component {2, 3} has total 6 + 1 = 7. Both totals are prime, so the answer is 2.
Constraints
1 <= n == values.length <= 10^40 <= values[i] <= 10^50 <= edges.length <= 2 * 10^4edges[j].length == 20 <= edges[j][0], edges[j][1] <= n - 1edges[j][0] != edges[j][1]- No two edges join the same pair of vertices.