C++ Algorithm: Connectivity

[Aaron Vienneau]

I'm reading the first chapter of Algorithms in C++: Part 1 - 4 Fundamentals, Data Structures, Sorting, Searching and have a question regarding an exercise they've given.

The exercise question is this:

Q) Describe a simple method for counting the number of sets remaining after using the union and find operations to solve the connectivity problem as described in the text.

The only answer I can think of is: For every union you make, the number of sets remaining decreases by 1.

I'm not sure if that's the answer they're looking for because there's no solutions manual or answer guide at the back.

Here is the PDF format of the book I'm reading, should you need additional reference: http://www.cs.princeton.edu/courses/archive/spr09/cos226/handouts/Algs3Ch1.pdf

[Zhuge]

That sounds like half a good answer to me. I'd have to complain that you are using the variable 'sets' without initializing it, however. ;) In other words, what does the value of 'sets' start at?

[Aaron Vienneau]

Hehehe.

Sets starts at N. Where N is the number of items to connect. For every union operation, the number of sets decreases by 1.

int itemsToConnect = 10;
int itemSets = itemsToConnect;

if( union( 3, 4) ) // ints are two "items" to connect
itemSets--;

Is that better or worse? Heh.