desperateboy12344's blog

By desperateboy12344, history, 3 months ago, In English

Guys I need your help with this weird graph problem. Given a graph N nodes and M undirected edges (N,M <= 10^5). For a connected component (A connected component is a where there's always a path between any two nodes in this component, such that the path only uses nodes in this component)

Define its value : size(C) * min_degree(C).

size(C) is the size of the connected component

min_degree(C) is the minimum degree of all of the nodes in this component. (Only nodes in this component are counted towards degree)

Find the max value over all of the components.

Example :

N = 8,M = 10 1 2

1 3

1 4

2 3

2 4

3 4

1 5

2 6

3 7

4 8

. Maximum value is 12, since we choose (1,2,3,4), minimum degree is 3, size is 4

Sorry for my broken english guys. I need you help!!!!. And thank you in advance for any help!!!!