c++ - 连接问题

Question

我需要知道我是否正确阅读了这个问题。我正在准备面试，我想我需要提高阅读理解能力。

问题说明:

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.

我个人认为我没有解决下面代码中的传递性部分，但我倾向于让事情变得比他们需要的更复杂。我可以从“C++ 中的算法”中得到这个问题的第二个解释吗？

/* 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 */ }

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

更新:1

好吧，我想我想出了一个我喜欢的解决方案。花了我很长时间，这对面试不利，但我还是明白了。

#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.push( 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 

Answer 1

当您输入对时，您不会检查传递性，也不会检查路径是否正确输入。

如果您使用了 Boost 的图形库，您可以创建一个无向图并以深度优先搜索 (DFS) 顺序遍历它:

// 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;
}