Connecting the special nodes

5

1 votes
Algorithms, Breadth First Search, Depth First Search, Graphs, Hard, Priority queue, dsu
Problem

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

1N105

1M2×105

  • K 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.
Sample Input
12 7 2
1 2
1 3
4 5
4 6
5 7
9 10
11 12
1 4
Sample Output
32 28
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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.

Contributers:
Editor Image

?