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 the 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.
Input format
- First line: Three integers \(N,\ M,\ and\ K\) representing the number of nodes, number of edges, and number of special nodes in the graph respectively
- Next \(M\) lines: Two integers \(u\ and\ v\) representing an undirected edge from the node \(u\) to node \(v\)
- Next line: An empty line
- Next line: \(K\) space-separated integers each representing the special nodes in a connected component
Output format
Print the maximum number of new edges that can be added to the graph and the minimum cost of doing so.
Constraints
\(1 ≤ N ≤ 10^{5}\)
\(1 ≤ M ≤ 2 \times 10^{5}\)
- \(K \leq\) 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.
12 7 2 1 2 1 3 4 5 4 6 5 7 9 10 11 12 1 4
32 28
The given graph consist of 5 connected components.\( (1, 2, 3), (4, 5, 6, 7), (8), (9, 10), (11, 12)\).
1 is the special node in \((1, 2, 3)\) and 4 is the special node in \((4, 5, 6, 7)\).
There is no special node in \((8), (9, 10), (11, 12)\).
For \((1, 2, 3)\):-
We can add 1 edge from 2 to 3, cost = 0 (same component).
For \((4, 5, 6, 7)\):-
We will add 3 edges from 6 to 5, 6 to 7 and 4 to 7. Now we can't add more edges to this component, cost = 0 (same component).
For the remaining nodes (without special nodes):-
We will first connect $$8$$ and \((11, 12)\) with cost 2 and 2 edges.
Then \((8, 11, 12)\) and \((9, 10)\) with cost 6 and 6 edges. (product of their sizes).
Now we have all the non special nodes completely connected.
We can now connect all the 5 non special nodes to the component \((4, 5, 6, 7)\) with cost 20 and 20 edges.
Hence total cost is 28 and maximum number of edges that can be added are 32.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor