擅长:python、mysql、java
<p>你的算法有缺陷。考虑这个例子:</p>
<pre><code>11110
01010
10010
11101
</code></pre>
<p>你的算法有2个组件,而它只有1个组件。在</p>
<p>为了测试,我使用了您代码的这个稍微修改过的版本。在</p>
^{pr2}$
<p>让我试着用文字来解释你的算法(用图形而不是网格)。在</p>
<ul>
<li>Set'roots'为空集。在</li>
<li>迭代图中的节点。
<ul>
<li>对于一个节点n,看看它所有的邻居已经处理过了。把这个集合称为A</li>
<li>如果A为空,则选择一个新值k,将v[node]设置为k,并将k添加到根中。在</li>
<li>否则,设k为A中节点v[node]的最小值。用v[x]从A中每个x的根中移除v[x]!=k</li>
</ul></li>
<li>成分数是根的元素数。在</li>
</ul>
<p>(您的<code>tree</code>与我的<code>roots</code>相同:请注意,您从不使用<code>tree[]</code>元素的值,只使用它们是否为0。。。这只是实现一个集合)</p>
<p>它类似于union find,只是它假定在合并两个组件时,v[]值较高的那个组件以前从未与另一个组件合并。在反例中,这是被利用的,因为中间列中的两个0已与其左侧的0合并。在</p>