Loading...
Loading...
You are given an integer n and a list edges describing an undirected graph on nodes labeled 1 to n. Each element in edges contains [u, v, c] meaning nodes u and v are joined by an edge of color c.
Two nodes are in the same color-c component if you can walk from one to the other using only edges of color c. A node belongs to a color-c component only if it touches at least one edge of color c, so every component has at least two nodes. Components of different colors are always separate, even when they share nodes.
The size of a component is the number of nodes in it. The score of a component is the product of its two largest node labels.
Look at the components of every color and find the largest size. Return the highest score among the components that have that size.
Note that the same pair of nodes can appear in edges more than once.
Input: n = 10
edges = [[ 1, 2, 51],
[ 7, 3, 51],
[ 5, 6, 51],
[10, 8, 51],
[ 6, 9, 51],
[ 2, 3, 51]]
Output: 21
Explanation: Every edge has color 51. Its components are {1, 2, 3, 7}, {5, 6, 9}, and {8, 10}. Node 4 touches no edge, so it is in no component. The largest component is {1, 2, 3, 7} with 4 nodes. Its two largest labels are 7 and 3, so the answer is 7 * 3 = 21.
Input: n = 6
edges = [[1, 2, 1],
[2, 3, 2],
[4, 5, 1]]
Output: 20
Explanation: Color 1 has the components {1, 2} and {4, 5}. Color 2 has the component {2, 3}. Node 2 is in a color-1 component and a color-2 component, but those stay separate. All three components have 2 nodes. Their scores are 2, 20, and 6, so the answer is 20.
Input: n = 6
edges = [[1, 2, 1],
[2, 3, 1],
[3, 1, 1],
[1, 2, 1],
[4, 6, 2],
[6, 1, 2],
[1, 3, 2]]
Output: 24
Explanation: Color 1 has the component {1, 2, 3}. It has 4 edges but only 3 nodes. Color 2 has the component {1, 3, 4, 6} with 4 nodes. That is the largest size, so the answer is 6 * 4 = 24.
edges.length ≤105edges[i] = [u, v, c] with 1≤u,v≤n and u=v