Connecting the special nodes
Practice
5 (1 votes)
Algorithms
Breadth first search
Depth first search
Graphs
Hard
Priority queue
Dsu
Problem
81% Success 1047 Attempts 50 Points 1s Time Limit 256MB Memory 1024 KB Max Code

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.

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

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
7 votes
Tags:
Maximum Bipartite MatchingAlgorithmsDepth First SearchGraphs
Points:50
4 votes
Tags:
Dynamic ProgrammingAlgorithmsGraphsDepth First Search
Points:50
11 votes
Tags:
Fenwick TreeGraphsDepth First SearchDisjoint Set UnionAlgorithms