Connectivity Problem

      Suppose that we are given a sequence of pairs of integers, where each integer represents an object of some type and we are to interpret the pair p-q as meaning “p is connected to q.” We assume the relation “is connected to” to be transitive: If p is connected to q, and q is connected to r, then p is connected to r. Our goal is to write a program inputs a pair p-q, it should output the pair only if the pairs it has seen to that point do not imply that p is connected to q. If the previous pairs do imply that p is connected to q, then the program should ignore p-q and should proceed to input the next pair. Figure 1.1 gives an example of this process.

3-4                      3-4

4-9                      4-9

8-0                      8-0

2-3                      2-3

5-6                      5-6

2-9                                                  2-3-4-9

5-9                      5-9

7-3                      7-3

4-8                      4-8

5-6                                                  5-6

0-2                                                  0-8-4-3-2

6-1                      6-1

 

Figure 1.1 Connectivity example

Given a sequence of pairs of integers representing connections between objects (left), the task of a connectivity algorithm is to output those pairs that provide new connections (center). For example, the pair 2-9 is not part of the output because the connection 2-3-4-9 is implied by previous connections (this evidence is shown at right)

更多内容看附件吧......

（附件中包含文档和源码)

文件:	connectivity problem.rar
大小:	928KB
下载:	下载