Computer network
Time limit2sMemory limit512 MB
Given a directed graph, find the minimum number of source computers that reach all nodes, and the minimum edges to add to make it strongly connected.
- Level
Medium7 of 10
- Topics
- Graph, DFS, Greedy, Implementation
- Solved
- No attempts yet
Problem
A computer network consists of N computers, numbered 0 to N-1. When a computer receives a message, it forwards the message to some other computers. A message sent from computer X may reach computer Y even when a message sent from Y does not reach X. The administrators want to know the minimum number of computers that must be chosen as message sources so that a message reaches every computer in the network.
To improve message delivery, they decide to extend the network by adding new connections between some computers, so that a message sent from any computer reaches all the others. For this, they need the minimum number of new connections to add so that every computer can serve as the source for distributing a message.
Write a program cnet that finds the minimum number of computers from which a message must be sent to reach all computers in the network, and the minimum number of new connections to add so that a message sent from any computer reaches every other computer in the network.
Input
The first line of the standard input contains two integers N and M, the number of computers and the number of connections between them. Each of the next M lines describes one connection: the first number is the computer that sends the message, the second is the computer that receives it.
Output
On a single line of the standard output, print two integers: the minimum number of computers that serve as sources to distribute a message to the whole network, and the minimum number of additional connections needed so that a message sent from any chosen computer reaches all the others.
Constraints
- 1 < N ≤ 1 600
- 0 ≤ M ≤ 120 000