Maximum Common Companies :
Difficulty Level : Medium
Submissions : 631
Asked In :
Marks :50
: 4 | : 3
There are $$$n$$$ friends, numbered from $$$1$$$ to $$$n$$$, who buy wholesale products from different companies. There are $$$m$$$ pairs of friends where each pair of friends is connected by the common company they buy products from. Companies are numbered from 1 to 100.
Note that if $$$a$$$ and $$$b$$$ are connected by a company $$$c$$$, and $$$b$$$ and $$$d$$$ are also connected by the company $$$c$$$, then $$$a$$$ and $$$d$$$ are also connected by the company $$$c$$$. Find the maximal product of $$$a$$$ and $$$b$$$ that share the largest group of friends which is connected by a common company.
The first line of input consists of 2 space separated integers $$$-$$$ $$$n$$$ and $$$m$$$ $$$(1 \leq n,m \leq 10^5)$$$. Each of the next $$$m$$$ lines consist of 3 space separated integers $$$u$$$, $$$v$$$ and $$$w$$$, which denotes that the friends numbered $$$u$$$ and $$$v$$$ are connected by the company numbered $$$w$$$. $$$(1 \leq u,v \leq n)$$$ $$$(1 \leq w \leq 100)$$$
The output should consist of a single integer $$$-$$$ the maximal product.
5 5 1 2 1 2 3 1 1 3 1 3 4 2 4 5 2
20
