Connectivity Problem

I need to know if I am reading this problem correctly. I am preparing for an interview, and I need to brush up on my reading comprehension skills I guess.

The problem states:

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 to filter out extraneous pairs from the set: When the 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.

I personally, don't think I have addressed the transitivity portion in the code below, but then I have the tendency to make things more complicated than they need to be. Can I get a second interpretation of what this question from "Algorithms in C++" is asking.

/* 1 */ #include <iostream>
/* 2 */ #include <set>
/* 3 */ #include <algorithm>
/* 4 */ 
/* 5 */ using namespace std;
/* 6 */ 
/* 7 */ #define PAIRS 7
/* 8 */ 
/* 9 */ pair<int,int> pair_list[PAIRS] = {
/*10 */     pair<int,int>(0,2),
/*11 */     pair<int,int>(1,4),
/*12 */     pair<int,int>(2,5),
/*13 */     pair<int,int>(3,6),
/*14 */     pair<int,int>(0,4),
/*15 */     pair<int,int>(6,0),
/*16 */     pair<int,int>(2,0) 
/*17 */ };
/*18 */ 
/*19 */ void print( const pair<int,int> &out ) {
/*20 */     cout << "<" << out.first << ", " << out.second << ">" << endl;
/*21 */ }
/*22 */ 
/*23 */ bool contains( set<pair<int,int> > &_set, pair<int,int> &ordered_pair ) {
/*24 */     set<pair<int,int> >::iterator find = _set.find( ordered_pair );
/*25 */     bool ret = false;
/*26 */     if( find != _set.end( ) ) {
/*27 */         ret = true;
/*28 */     }
/*29 */     return ret;
/*30 */ }
/*31 */ 
/*32 */ int main( int argc, char **argv ) {
/*33 */     set<pair<int,int> > SET;
/*34 */     SET.clear( ); 
/*35 */     pair<int,int> *iter = &pair_list[0]; 
/*36 */     while( iter != &pair_list[PAIRS-1] ) {
/*37 */         if( !contains( SET,(*iter) ) ){
/*38 */                 SET.insert( (*iter) );
/*39 */         }
/*40 */         iter++;
/*41 */     }
/*42 */     
/*43 */     for_each( SET.begin( ), SET.end( ), print );
/*44 */     return ( 0 );
/*45 */ }

==================================================================================

UPDATE: 1

Okay I think I came up with a solution I like. Took me way to long, and that is going to be bad for interviews, but I still got it.

#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <iterator>

using namespace std;

void print_set( set<int>* _set ) {
    copy( _set->begin( ), _set->end( ), ostream_iterator<int>(cout, " ") );
    cout << endl;
}

void print_sets( set<set<int>*> _sets ) {
    for_each( _sets.begin( ), _sets.end( ), print_set );
}

void connectivity( queue<pair<int,int> > pairs ) {
    set<set<int>* > connected_items;
    while( pairs.size( ) ) {
        int first = pairs.front( ).first;
        int second = pairs.front( ).second;
        set<set<int>* >::iterator S=connected_items.begin( );
        bool found = false;
        bool dupli = false;
        set<int>* adj = new set<int>;
        while( S != connected_items.end( ) ) { //Go through all connected sets
            set<int>::iterator f=(*S)->find( first );
            set<int>::iterator s=(*S)->find( second );
            if( f!=(*S)->end( )&&s!=(*S)->end( ) ) {
                S++;
                dupli = true;
                continue;
            }
            if( f!=(*S)->end( )||s!=(*S)->end( ) ) {
                found = true;
                adj->insert( first );
                adj->insert( second );
                //copy( (*S)->begin( ), (*S)->end( ), ostream_iterator<int>( cout," ")  );
                set<int>::iterator num = (*S)->begin( );
                while( num != (*S)->end( ) ) {
                    adj->insert( (*num) );
                    num++;
                }
                connected_items.erase( S );
            }
            S++;
        }
        if( !found&&!dupli ) {
            set<int>* insert = new set<int>;
            connected_items.insert( insert );
            insert->insert( first );
            insert->insert( second );
        } else {
            connected_items.insert( adj );
        }
        pairs.pop( );
    }
    print_sets( connected_items );
}

int main( int argc, char **argv ) {
    queue<pair<int,int> > pairs;
    pairs.push( pair<int,int>( 1,2 ) );
    pairs.pu开发者_开发技巧sh( pair<int,int>( 2,3 ) );
    pairs.push( pair<int,int>( 2,4 ) );
    pairs.push( pair<int,int>( 2,5 ) );
    pairs.push( pair<int,int>( 6,7 ) );
    pairs.push( pair<int,int>( 6,8 ) );
    pairs.push( pair<int,int>( 6,9 ) );
    pairs.push( pair<int,int>( 9,10 ) );
    pairs.push( pair<int,int>( 11,12 ) );
    pairs.push( pair<int,int>( 12,13 ) );
    pairs.push( pair<int,int>( 14,15 ) );
    pairs.push( pair<int,int>( 2,12) );
    pairs.push( pair<int,int>( 2,1) );
    connectivity( pairs );
}


[mehoggan@desktop Connectivity]$ g++ -o connected -Wall connected.cpp; ./connected
6 7 8 9 10 
14 15 
1 2 3 4 5 11 12 13 

---

While you are inputting the pairs, you do not check for transitivity nor if the path is correctly entered.

If you used Boost's Graph library, you could create an undirected graph and traverse it in depth-first-search (DFS) order:

// Boost DFS example on an undirected graph.
// Create a sample graph, traverse its nodes
// in DFS order and print out their values.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>
using namespace std;

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> MyGraph;
typedef boost::graph_traits<MyGraph>::vertex_descriptor MyVertex;

class MyVisitor : public boost::default_dfs_visitor
{
public:
  void discover_vertex(MyVertex v, const MyGraph& g) const
  {
    cerr << v << endl;
    return;
  }
};

int main()
{
  MyGraph g;
  boost::add_edge(0, 1, g);
  boost::add_edge(0, 2, g);
  boost::add_edge(1, 2, g);
  boost::add_edge(1, 3, g);

  MyVisitor vis;
  boost::depth_first_search(g, boost::visitor(vis));

  return 0;
}

---

No it's not correct.

Say the input is (1,2), (2,3), (1,3). Then the output should be (1,2), (2,3), while in your code it would be (1,2), (2,3), (3,1).

HINT: You are correct to use a set however ( in fact more than one ). The sets will contain integers, not pairs of integers. The integers in a set will all be connected to each other. (Hope that's not too much giving away the solution).

---

You aren't actually testing your function. According to the problem, the function should reject redundant pairs. But there are no redundant pairs in your data set. Try inserting (0,5) into the list after (2,5). This should be rejected, since we have already seen (0,2) and (2,5). (I would assume that they intend connectivity to be commutative, not just transitive, but this example does not require it.)

Once you do that, you'll see that your code fails the test. You use a function, contains (the clue is in the name) which checks to see whether a particular pair has been seen before, not whether it can be deduced from what has been seen before.

EDIT:
No, you didn't fix it. Read what I wrote above; you still don't test with a pair like (0,5), and once you do you'll see that your code still fails.

EDIT:
Sorry, my mistake. Your new code works. But if you don't mind my saying, you're making more work for yourself than necessary, and it's the kind of thing some interviewers notice. Take a look at this, for comparison:

void connectivity_adj(int first, int second,
                      set<set<int> > &connected_items){
  set<int> adj;
  adj.insert( first );
  adj.insert( second );

  for(set<set<int> >::iterator S=connected_items.begin( );
      S != connected_items.end( ); ++S){ //Go through all connected sets
          if( S->find(first) != S->end() || S->find( second ) != S->end( )){
        adj.insert(S->begin(), S->end());
        connected_items.erase( S );
      }
    }
  connected_items.insert( adj );
}

---

Assuming that, if a is connected to b, then b is connected to a, then this looks like it is supposed to be a question on http://en.wikipedia.org/wiki/Disjoint-set_data_structure. Note that the final improved version, with path compression, is more efficient than less specialised set structures.

---

Using sets is a good approach, but the mistake in your first solution is in keeping sets of pairs. This is why it does not address the transitivity requirement. The pairs 1-2 and 2-1 are seen as two different objects.

The solutions given in the book keep sets of individual nodes (instead of pairs of nodes). This allows you to keep track of whether two nodes are connected just by inclusion in the same set, regardless of their order. When two nodes are given as input, the sets they belong to are unioned together if they're not already members of the same set.

Here's the basic "quick find" solution:

#include <iostream>

static const int N = 10000;

void quickFind() {
    int i, p, q, id[N];
    for (i = 0; i < N; i++) id[i] = i;

    while (std::cin >> p >> q) {
        int t = id[p];
        if (t == id[q]) continue;  // find

        for (i = 0; i < N; i++) {  // union
            if (id[i] == t) id[i] = id[q];
        }
        std::cout << "   " << p << " " << q << std::endl;
    }
}

This works by initializing a bunch of "sets" in the array id to each have a single node with the unique values from 0 to 9999. The "find" operation is very simple. If two nodes (elements of the id array) have the same value, they are in the same set. The "union" operation loops through the array and updates the values in one set so they become a member of the other, effectively joining the two sets before the next input.