blocks|key|2022137|text|正如Jarod42所指出的，您需要由边缘列表定义的图的连接组件。下面是如何让那些使用STL的人。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2022138|构造一个邻接列表:一个map<int,+set<int>+>，它将每个整数映射到它在对中共同出现的整数集。这可以通过对向量进行一次迭代，将.second添加到.first's集合，将.first添加到.second's。|ordered-list-item|offset|length|style|CODE|2022139|遍历邻接列表的深度-优先.这有点复杂。初始化vector<set<int>+>。保留已处理的整数的set<int>+(最初为空)。循环遍历邻接列表的条目。对于未出现在已处理集合中的每个整数键，按照以下步骤构造下一个组件，并将其推回向量，然后与该组件合并更新处理过的整数集。|2022140|用整数键从2初始化一个stack<int>。初始化一个空的set<int>，即当前连接的组件。当堆栈不是空的时候，获取它的顶部整数并弹出它。如果该整数未出现在组件中，则执行以下操作。将整数插入组件中，然后在邻接列表中查找并将其所有邻居推到堆栈上。|2022141|entityMap^0|0|B|J|1X|7|27|6|2J|6|2S|7|0|M|H|1D|8|0|B|A|T|8|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@$E|Q|F|R|G|H]|$E|S|F|T|G|H]|$E|U|F|V|G|H]|$E|W|F|X|G|H]|$E|Y|F|Z|G|H]]|9|@]|A|$]]|$1|I|3|J|5|D|7|10|8|@$E|11|F|12|G|H]|$E|13|F|14|G|H]]|9|@]|A|$]]|$1|K|3|L|5|D|7|15|8|@$E|16|F|17|G|H]|$E|18|F|19|G|H]]|9|@]|A|$]]|$1|M|3|-4|5|6|7|1A|8|@]|9|@]|A|$]]]|N|$]]

As Jarod42 points out, you want the connected components of the graph defined by your edge list. Here's how to get those using the STL.

<ol>
<li>Construct an adjacency list: a <code>map&lt;int, set&lt;int&gt; &gt;</code> that maps each integer to the set of integers with which it co-occurs in a pair. This can be done with one iteration through the vector of pairs, adding <code>.second</code> to <code>.first</code>'s set and <code>.first</code> to <code>.second</code>'s.</li>
<li>Traverse the adjacency list depth-first. This is somewhat more complicated. Initialize the <code>vector&lt;set&lt;int&gt; &gt;</code>. Keep a <code>set&lt;int&gt;</code>, initially empty, of integers that have been processed. Loop through the entries of the adjacency list. For each integer key that does not appear in the processed set, construct the next component as follows and push it back onto the vector, then union-update the set of processed integers with the component.</li>
<li>Initialize a <code>stack&lt;int&gt;</code> with the integer key from 2. Initialize an empty <code>set&lt;int&gt;</code>, the current connected component. While the stack is not empty, grab its top integer and pop it. If this integer does not appear in the component, then do the following. Insert the integer into the component, then look it up in the adjacency list and push all of its neighbors onto the stack.</li>
</ol>

blocks|key|1023297|text|#include+<iostream>
#include+<set>
#include+<vector>
#include+<algorithm>
#include+<iterator>

typedef+std::set<std::pair<int,int>+>+SetOfPair;|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1023298|以及：|unstyled|1023299|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_)+%7C%7C+(+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);
++++++++++++++++%2B%2BindexCount;
++++++++++++}
++++++++++++sp.erase(+it);
++++++++}
++++++++%2B%2BcurrIdx;
++++}
++++return+std::set<int>(+componentIndices.begin(),+componentIndices.end());
}|1023300|1023301|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);
++++++++%2B%2BcomponentCount;
++++}
++++return+componentCount;
}|1023302|用法：|1023303|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;
++++++++%2B%2Bit;
++++}
++++return+0;
}|1023304|输出：|1023305|组分编号:3|1023306|1:8：|1023307|2:3:4:5：|1023308|9：|1023309|成功运行(总时间:61+RUN+)|1023310|网上汇编|offset|length|1023311|entityMap|0|LINK|mutability|MUTABLE|url|http://coliru.stacked-crooked.com/a/7b5e4c2ea0603429^0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|4|0|0^^$0|@$1|2|3|4|5|6|7|1D|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|1E|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|1F|8|@]|9|@]|A|$B|C]]|$1|I|3|E|5|F|7|1G|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|1H|8|@]|9|@]|A|$B|C]]|$1|L|3|M|5|F|7|1I|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|1J|8|@]|9|@]|A|$B|C]]|$1|P|3|Q|5|F|7|1K|8|@]|9|@]|A|$]]|$1|R|3|S|5|F|7|1L|8|@]|9|@]|A|$]]|$1|T|3|U|5|F|7|1M|8|@]|9|@]|A|$]]|$1|V|3|W|5|F|7|1N|8|@]|9|@]|A|$]]|$1|X|3|Y|5|F|7|1O|8|@]|9|@]|A|$]]|$1|Z|3|10|5|F|7|1P|8|@]|9|@]|A|$]]|$1|11|3|12|5|F|7|1Q|8|@]|9|@$13|1R|14|1S|1|1T]]|A|$]]|$1|15|3|-4|5|F|7|1U|8|@]|9|@]|A|$]]]|16|$17|$5|18|19|1A|A|$1B|1C]]]]

<pre><code>#include &lt;iostream&gt;
#include &lt;set&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
#include &lt;iterator&gt;

typedef std::set&lt;std::pair&lt;int,int&gt; &gt; SetOfPair;
</code></pre>

and:

<pre><code>struct pair_equal : std::unary_function&lt; std::pair&lt;int,int&gt;, bool&gt; {
 pair_equal(const int &amp;idx) : idx_(idx) {}
 bool operator()(const std::pair&lt;int,int&gt; &amp;arg) const { return 
 ( arg.first == idx_) || ( arg.second == idx_); }
 const int &amp;idx_;
};

std::set&lt;int&gt; connected_component( SetOfPair&amp; sp) {
 std::vector&lt;int&gt; 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 &lt; 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&lt;int&gt;( componentIndices.begin(), componentIndices.end());
}
</code></pre>

and:

<pre><code>int make_connected_components( SetOfPair sp, 
 std::vector&lt;std::set&lt;int&gt; &gt;&amp; result) {
 int componentCount = 0;
 while( !sp.empty()) {
 std::set&lt;int&gt; component = connected_component( sp);
 result.push_back( component);
 ++componentCount;
 }
 return componentCount;
}
</code></pre>

usage:

<pre><code>int main(int argc, char** argv) {

 SetOfPair sp;
 sp.insert( std::make_pair&lt;int, int&gt;( 1, 1));
 sp.insert( std::make_pair&lt;int, int&gt;( 3, 2));
 sp.insert( std::make_pair&lt;int, int&gt;( 5, 5));
 sp.insert( std::make_pair&lt;int, int&gt;( 5, 4));
 sp.insert( std::make_pair&lt;int, int&gt;( 4, 2));
 sp.insert( std::make_pair&lt;int, int&gt;( 1, 8));
 sp.insert( std::make_pair&lt;int, int&gt;( 9, 9));

 std::vector&lt;std::set&lt;int&gt; &gt; components;
 int numberOfComponents = make_connected_components( sp, components);

 /* results */
 std::cout &lt;&lt; "numberOfComponents:" &lt;&lt; numberOfComponents &lt;&lt; std::endl;
 std::vector&lt;std::set&lt;int&gt; &gt;::iterator it = components.begin();
 while ( it != components.end()) {
 std::copy( (*it).begin(), (*it).end(), 
 std::ostream_iterator&lt;int&gt;( std::cout, ":"));
 std::cout &lt;&lt; std::endl;
 ++it;
 }
 return 0;
}
</code></pre>

Output:

numberOfComponents:3

1:8:

2:3:4:5:

9:

RUN SUCCESSFUL (total time: 61ms)

<a href="http://coliru.stacked-crooked.com/a/7b5e4c2ea0603429" rel="nofollow">compiled online</a>

I have the following data structure:

<pre><code>set&lt; pair&lt;int, int&gt; &gt; data;
data = {&lt;1, 1&gt; ; &lt;3, 2&gt; ; &lt;5, 5&gt; ; &lt;5, 4&gt; ; &lt;4, 2&gt;, &lt;1, 8&gt;, &lt;9, 9&gt; }
</code></pre>

I would like to merge pairs which contain at least one common element and store the result in a vector of sets.

<pre><code>vector&lt; set&lt;int&gt; &gt; result;
result = [ {1, 8} ; {2, 3, 4, 5} ; {9} ]
</code></pre>

I know that there is a set_union in <code>&lt;algorithm&gt;</code> but how can we compute the "union" of pairs? Thanks!

Merge pairs that share one element in common

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我有以下数据结构：set< pair<int, int> > data;data = {<1, 1> ; <3, 2> ; <5, 5> ; <5, 4> ; <4, 2>, <1, 8>, <9, 9> }我希望合并包含至少一个公共元素的对，并将结果存储在集合向量中。vector< set<int> > result...

问共有一个元素的合并对
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问共有一个元素的合并对EN