共有一个元素的合并对
共有一个元素的合并对
提问于 2014-03-30 13:40:12
我有以下数据结构：
set< pair<int, int> > data;
data = {<1, 1> ; <3, 2> ; <5, 5> ; <5, 4> ; <4, 2>, <1, 8>, <9, 9> }我希望合并包含至少一个公共元素的对，并将结果存储在集合向量中。
vector< set<int> > result;
result = [ {1, 8} ; {2, 3, 4, 5} ; {9} ]我知道在set_union中有一个<algorithm>，但是我们如何计算对的“并”呢？谢谢!
回答 2
Stack Overflow用户
回答已采纳
发布于 2014-03-30 15:41:05
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <iterator>
typedef std::set<std::pair<int,int> > SetOfPair;以及：
struct pair_equal : std::unary_function< std::pair<int,int>, bool> {
pair_equal(const int &idx) : idx_(idx) {}
bool operator()(const std::pair<int,int> &arg) const { return
( arg.first == idx_) || ( arg.second == idx_); }
const int &idx_;
};
std::set<int> connected_component( SetOfPair& sp) {
std::vector<int> componentIndices;
componentIndices.push_back( (*(sp.begin())).first);
componentIndices.push_back( (*(sp.begin())).second);
int indexCount = 2;
int currIdx = 0;
SetOfPair::const_iterator it;
while ( currIdx < indexCount) {
while ( ( it = std::find_if( sp.begin(), sp.end(), pair_equal(
componentIndices[ currIdx]))) != sp.end()) {
/* new reachable index connected to this component found */
int newIdx = ( componentIndices[ currIdx] ==
(*it).first? (*it).second : (*it).first);
/* insert if not present already */
if ( std::find( componentIndices.begin(),
componentIndices.end(), newIdx) == componentIndices.end()) {
componentIndices.push_back( newIdx);
++indexCount;
}
sp.erase( it);
}
++currIdx;
}
return std::set<int>( componentIndices.begin(), componentIndices.end());
}以及：
int make_connected_components( SetOfPair sp,
std::vector<std::set<int> >& result) {
int componentCount = 0;
while( !sp.empty()) {
std::set<int> component = connected_component( sp);
result.push_back( component);
++componentCount;
}
return componentCount;
}用法：
int main(int argc, char** argv) {
SetOfPair sp;
sp.insert( std::make_pair<int, int>( 1, 1));
sp.insert( std::make_pair<int, int>( 3, 2));
sp.insert( std::make_pair<int, int>( 5, 5));
sp.insert( std::make_pair<int, int>( 5, 4));
sp.insert( std::make_pair<int, int>( 4, 2));
sp.insert( std::make_pair<int, int>( 1, 8));
sp.insert( std::make_pair<int, int>( 9, 9));
std::vector<std::set<int> > components;
int numberOfComponents = make_connected_components( sp, components);
/* results */
std::cout << "numberOfComponents:" << numberOfComponents << std::endl;
std::vector<std::set<int> >::iterator it = components.begin();
while ( it != components.end()) {
std::copy( (*it).begin(), (*it).end(),
std::ostream_iterator<int>( std::cout, ":"));
std::cout << std::endl;
++it;
}
return 0;
}输出：
组分编号:3
1:8：
2:3:4:5：
9：
成功运行(总时间:61 RUN )
网上汇编
Stack Overflow用户
发布于 2014-03-30 15:14:42
正如Jarod42所指出的，您需要由边缘列表定义的图的连接组件。下面是如何让那些使用STL的人。
- 构造一个邻接列表:一个
map<int, set<int> >，它将每个整数映射到它在对中共同出现的整数集。这可以通过对向量进行一次迭代，将.second添加到.first's集合，将.first添加到.second's。 - 遍历邻接列表的深度-优先.这有点复杂。初始化
vector<set<int> >。保留已处理的整数的set<int>(最初为空)。循环遍历邻接列表的条目。对于未出现在已处理集合中的每个整数键，按照以下步骤构造下一个组件，并将其推回向量，然后与该组件合并更新处理过的整数集。 - 用整数键从2初始化一个
stack<int>。初始化一个空的set<int>，即当前连接的组件。当堆栈不是空的时候，获取它的顶部整数并弹出它。如果该整数未出现在组件中，则执行以下操作。将整数插入组件中，然后在邻接列表中查找并将其所有邻居推到堆栈上。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22744644
复制相关文章
相似问题
腾讯云开发者
