Homework 05 Solution

Description
As each team of exploeres from Oganesson Dynamics arrives at their destination, the first thing they want to do is setup a communications base. But where should they put it?

To decide, they build a graph of the area. Each node represents a work site, and each edge indicates two sites that are close enough to communicate if one of them has the communications base. In fact, pairs of sites can relay through the base to communicate, as long as they are both connected to it. It can be slow, but it works well.

You must determine where to put the base such that the MOST pairs of sites can communicate.

Input Format

The first line contains N, the number of sites being analyzed, and M, the number of pairs (edges) that could potentially communicate.
The next M lines each have two values identifying all pairs of sites that could communicate with a base station at one of them.
Constraints

1 ≤ N ≤ 200
1 ≤ M ≤ 10,000
0 ≤ site IDs < N
Output Format

Output the count of how many PAIRS of sites would be able to communicate if the communications base were placed in the optimal position.

Example 0
Sample Input

5 7
0 1
0 2
0 3
1 2
1 3
1 4
2 3
Sample Output

 10
Explanation

If a communications node is placed at size 1, it will connect to 0, 2, 3, and 4.

This means that there are 10 pairs that can communicate. Node 1 can directly communicate with each of the four others PLUS it can relay communications between (0,2), (0,3), (0,4), (2,3), (2,4), and (3,4).




Description
Some teams from Oganesson dynamics were sent with two communications bases. These bases must be connected to each other by an edge, but have the ability to relay messages through one another, connecting any of their neighbors and broadly expanding the range covered.

You must determine where to put the two bases such that the most pairs of sites can communicate.

Input Format

The first line contains N, the number of sites being analyzed and M, the number of pairs of sites that could potentially communicate, including through related messages.
The next M lines each have two values identifying all pairs of sites that could directly communicate if a base station is at one of them.
Constraints

1 ≤ N ≤ 200
1 ≤ M ≤ 10,000
0 ≤ site IDs < N
Output Format

Output the count of how many PAIRS of sites would be able to communicate if the communications bases were placed in the optimal position.

Example 0
Sample Input

5 6
0 1
0 2
0 4
1 4
2 3
2 4
Sample Output

 10
Explanation

If communications nodes are placed at sites 0 and 2, they can facilitate communication among all 5 sites, this is allowed because sites 0 and 2 are connected to each other. On top of that, site 0 is connected to 1 and 4, while site 2 is connected to 3 and 4.

With fives sites, there are (5 x 4)/2 = 10 pairs.



Description
Over time, exploration teams will build more communications bases and set them up at each site. However, there's still a problem! Some sites simply cannot be connected at all, no matter how many bases are used.

You must analyze a connectivity network and identify how many distinct (unconnected) components a graph is divided into.

Input Format

The first line contains N, the number of sites being analyzed, and M, the number of connections that will exist when all nodes are in place.
The next M lines each have two values identifying a pair of connected sites.
Constraints

1 ≤ N ≤ 200
1 ≤ M ≤ 10,000
0 ≤ site IDs < N
Output Format

Print the number of indepent site clusters in the input graph.

Example 0
Sample Input

9 10
0 3
0 4
0 5
1 2
1 6
1 8
2 8
3 7
4 7
6 8
Sample Output

 2
Explanation

This graph looks like this:






Description
Great news! Oganesson Dynamics has worked out the technology to provide instantaneous communications between two sites, MUCH faster than the old system. The problem is that it is quite expensive to setup, especially since a sending unit and receiving unit must be built for each site and the price varies depending on how far apart they are and if there are any obstacles in between.

Given a graph where nodes represent sites and edges provide the cost of connecting two sites, determine the cheapest it would be to make sure that ALL of the sites can communicate with one another. (Again, relaying of information is allowed, and much faster this time!)

Input Format

The first line contains N, the number of sites, and M, the number of possible pairs of sites that could communicate.
The next M lines each have three integer values. The first two identify the two sites involved, while the third provides the cost to setup a communications channel.
All graphs are gauranteed to be connected.
Constraints

1 ≤ N ≤ 200
1 ≤ M ≤ 10,000
0 ≤ cost to setup a communication channel ≤ 1,000,000
0 ≤ site IDs < N
Output Format

A single value indicating the minimum total cost to setup communications

Example 0
Sample Input

5 6
0 1 5
0 2 10
0 3 2
1 3 3
1 4 8
3 4 1
Sample Output

 16
Explanation

The graph is as follows, with the minimum-cost communication channels highlighted:



As such, the total cost is 1 + 2 + 3 + 10 = 16.




Description
Oganesson Dynamics wants to ensure that all of its communications within a network remain private, but this requires extra equipment for at least one end of each communicating pair of sites.

Given a graph where vertices represent work sites and edges represent pairs of sites that must be able to communicate securely, what are the fewest work sites that can have security-monitoring nodes to guarantee that each pair has at least one?

Hint: you will need to use a branch-and-bound approach to solving this problem.

NOTE: For this problem, your program must be guaranteed to output the correct answer (or timeout in the process of searching). If your program's output is incorrect for a single test case, it will receive 0 credit on this problem (regardless of how many other test cases it passes). Timing out is allowed, however. Test cases on which you time out will result in no points from that test case, but will not zero out points earned on test cases where your program returned the correct output.

Input Format

The first line contains two values: the number of work sites (N) and the number of pairs of sites that must be able to communicate securely (M).
The next M lines each describe a pair of communicating sites, indicating the unique id of each.
Constraints

1 ≤ N ≤ 200
1 ≤ M ≤ 10,000
0 ≤ Work Site IDs < N
Output Format

A single number indicating the minimum number of work sites that must have security monitoring nodes to ensure that at least one exists for every communicating pair.

Example 0
Sample Input

5 6
0 1
0 2
0 4
1 4
2 3
2 4
Sample Output

 3
Explanation

Security nodes at sites 0, 1, and 2 will ensure that all communications in the network are safe.