Connecting The Special Nodes :
Difficulty Level : Hard
Submissions : 95
Asked In :
Marks :100
: 1 | : 0
You are given a graph of N nodes. The graph consists of connected components. Some of the connected components contain a special node and each component contains at most one special node. You are required to maximize the number of edges in the given graph such that it follows these constraints:
No self-loop or multiple edges should be present No connected components with more than one special node should be present
Each node in the graph should belong to a component with exactly one special node
If you add an edge between two nodes that belong to the same component in the graph, then the total cost involved is 0. Whereas, if you connect two nodes that belong to different components, then the cost is equal to the product of the sizes of both components.
Your task is to maximize the number of new edges in the graph and calculate the minimum cost that will be involved in performing the required task.
First line: Three integers N,M,K representing the number of nodes, number of edges, and number of special nodes in the graph respectively ($$$1 \le N \le 10^5$$$)and ($$$1 \le N \le 20^5$$$)
Next M lines: Two integers representing an undirected edge from the node u to node v
Next line: K space-separated integers each representing the special nodes in a connected component
Print the maximum number of new edges that can be added to the graph and the minimum cost of doing so.
12 7 2 1 2 1 3 4 5 4 6 5 7 9 10 11 12 1 4
32 28
K $$$\le$$$ the total number of connected components present in the graph.
It is guaranteed that for any connected component at most one special node exists.
The given graph does not contain any self-loops or multiple edges.
