Aurora Wednesday 18:30 Python Practice 22.12.07.

Question 1:

Please use Disjoint Set learned in the class to solve the following question:

There are so many different religions in the world today that it is difficult to keep track of them all. You are interested in finding out how many different religions students in your university believe in.

You know that there are n students in your university (0 < n <= 50000). It is infeasible for you to ask every student their religious beliefs. Furthermore, many students are not comfortable expressing their beliefs. One way to avoid these problems is to ask m (0 <= m <= n(n-1)/2) pairs of students and ask them whether they believe in the same religion (e.g. they may know if they both attend the same church). From this data, you may not know what each person believes in, but you can get an idea of the upper bound of how many different religions can be possibly represented on campus. You may assume that each student subscribes to at most one religion.

Input
The input consists of a number of cases. Each case starts with a line specifying the integers n and m. The next m lines each consists of two integers i and j, specifying that students i and j believe in the same religion. The students are numbered 1 to n. The end of input is specified by a line in which n = m = 0.

Output
For each test case, print on a single line the case number (starting with 1) followed by the maximum number of different religions that the students in the university believe in.

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

Sample Output
Case 1: 1
Case 2: 7

Question 2:
A construction company owns a large piece of real estate within the state of Florida. Recently, the company decided to develop this property. Upon inspection of the property, however, it was revealed that the land, at various locations, contained bodies of water. This came as a shock to the owners of the company, for they were from out of state and not familiar with wetlands of Florida. The situation was very grave and the owners not knowing that such bodies of water can be converted to beautiful lakes that will increase the value of the land around them, were about to abandon the construction project. Fortunately, this fact was brought to the owners’ attention by a smart FIU graduate who worked for the company and consequently the construction project started.

The engineers divided the construction site by a grid into uniform square cells such that each square cell entirely contained either water or land. (How they did it, of course, is anybody’s guess.) Now, the question that the engineers are to answer is the following: “Given the row and column number of a grid cell that contains water, what is the area of the lake containing that cell.” (an area is measured by number of grid cells it contains. Diagonal cells are considered to be adjacent.)

You are to write a program to answer this question!

Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The input consists of 0 < n ≤ 99 lines each containing 0 < m ≤ 99 character long sequence of ‘L’s and ‘W’s followed by k > 0 lines each containing a pair of integers i and j. The first n lines will represent the n×m grid covering the land where a ‘W’/‘L’ at the c-th character of the r-th line indicates water/land within the cell at row r and column c of the grid. The pairs of integers on the last k lines, each represent the row and column numbers of some grid cell that contains water.

Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

The output for each pair of integers, i and j, on the last k lines of input, consists of an integer, on a separate line, indicating the area of the lake containing the grid cell, at row i and column j of the grid.

Sample Input
1

LLLLLLLLL
LLWWLLWLL
LWWLLLLLL
LWWWLWWLL
LLLWWWLLL
LLLLLLLLL
LLLWWLLWL
LLWLWLLLL
LLLLLLLLL
3 2
7 5

Sample Output
12
4