#include<iostream> #include<cstring> using namespace std; int pre[101]; int u[101],v[101],edge[101]; //u,v分别为两个点，edge为两个点之间的边 int m,n; int find(int x) { 
讯享网</span><span style="color: rgba(0, 0, 255, 1)">int</span> root =<span style="color: rgba(0, 0, 0, 1)"> x; </span><span style="color: rgba(0, 0, 255, 1)">while</span>(pre[root]!=<span style="color: rgba(0, 0, 0, 1)">root) root </span>=<span style="color: rgba(0, 0, 0, 1)"> pre[root]; </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">路径压缩</span> <span style="color: rgba(0, 0, 255, 1)">int</span><span style="color: rgba(0, 0, 0, 1)"> i,j; i </span>=<span style="color: rgba(0, 0, 0, 1)"> x; </span><span style="color: rgba(0, 0, 255, 1)">while</span>(pre[i]!=<span style="color: rgba(0, 0, 0, 1)">root) { j </span>=<span style="color: rgba(0, 0, 0, 1)"> i; i </span>=<span style="color: rgba(0, 0, 0, 1)"> pre[i]; pre[j] </span>=<span style="color: rgba(0, 0, 0, 1)"> root; } </span><span style="color: rgba(0, 0, 255, 1)">return</span><span style="color: rgba(0, 0, 0, 1)"> root; 
 }
讯享网 void kruskal() //最小生成树，Kruskal算法 { 
cout</span>&lt;&lt;<span style="color: rgba(128, 0, 0, 1)">"</span><span style="color: rgba(128, 0, 0, 1)">Kruskal:</span><span style="color: rgba(128, 0, 0, 1)">"</span>&lt;&lt;<span style="color: rgba(0, 0, 0, 1)">endl; </span><span style="color: rgba(0, 0, 255, 1)">int</span><span style="color: rgba(0, 0, 0, 1)"> i,total,min,minnum,fu,fv; total </span>= n-<span style="color: rgba(128, 0, 128, 1)">1</span><span style="color: rgba(0, 0, 0, 1)">; </span><span style="color: rgba(0, 0, 255, 1)">while</span>(total&gt;<span style="color: rgba(128, 0, 128, 1)">0</span><span style="color: rgba(0, 0, 0, 1)">) { min </span>= <span style="color: rgba(128, 0, 128, 1)"></span><span style="color: rgba(0, 0, 0, 1)">; </span><span style="color: rgba(0, 0, 255, 1)">for</span>(i=<span style="color: rgba(128, 0, 128, 1)">1</span>;i&lt;=m;i++) <span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">找最小值</span> 
  { 
讯享网 </span><span style="color: rgba(0, 0, 255, 1)">if</span>(u[i] == -<span style="color: rgba(128, 0, 128, 1)">1</span>||v[i] == -<span style="color: rgba(128, 0, 128, 1)">1</span><span style="color: rgba(0, 0, 0, 1)">) </span><span style="color: rgba(0, 0, 255, 1)">continue</span><span style="color: rgba(0, 0, 0, 1)">; </span><span style="color: rgba(0, 0, 255, 1)">if</span>(edge[i]&lt;<span style="color: rgba(0, 0, 0, 1)">min) { min </span>=<span style="color: rgba(0, 0, 0, 1)"> edge[i]; minnum </span>=<span style="color: rgba(0, 0, 0, 1)"> i; } } fu </span>=<span style="color: rgba(0, 0, 0, 1)"> find(u[minnum]); fv </span>=<span style="color: rgba(0, 0, 0, 1)"> find(v[minnum]); </span><span style="color: rgba(0, 0, 255, 1)">if</span>(fu!=fv) <span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">不连通,就连接两个点</span> 
  { 
 cout</span>&lt;&lt;u[minnum]&lt;&lt;<span style="color: rgba(128, 0, 0, 1)">"</span><span style="color: rgba(128, 0, 0, 1)">,</span><span style="color: rgba(128, 0, 0, 1)">"</span>&lt;&lt;v[minnum]&lt;&lt;<span style="color: rgba(128, 0, 0, 1)">"</span><span style="color: rgba(128, 0, 0, 1)">:</span><span style="color: rgba(128, 0, 0, 1)">"</span>&lt;&lt;edge[minnum]&lt;&lt;<span style="color: rgba(0, 0, 0, 1)">endl; pre[fu] </span>=<span style="color: rgba(0, 0, 0, 1)"> fv; total</span>--<span style="color: rgba(0, 0, 0, 1)">; } edge[minnum] </span>= <span style="color: rgba(128, 0, 128, 1)"></span>; <span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">改变已经找到的最小值</span> u[minnum] = -<span style="color: rgba(128, 0, 128, 1)">1</span><span style="color: rgba(0, 0, 0, 1)">; v[minnum] </span>= -<span style="color: rgba(128, 0, 128, 1)">1</span><span style="color: rgba(0, 0, 0, 1)">; } 
 } int main() { 
讯享网cin</span>&gt;&gt;n&gt;&gt;<span style="color: rgba(0, 0, 0, 1)">m; </span><span style="color: rgba(0, 0, 255, 1)">int</span><span style="color: rgba(0, 0, 0, 1)"> i,a,b,tem; </span><span style="color: rgba(0, 0, 255, 1)">for</span>(i=<span style="color: rgba(128, 0, 128, 1)">1</span>;i&lt;=n;i++<span style="color: rgba(0, 0, 0, 1)">) pre[i] </span>=<span style="color: rgba(0, 0, 0, 1)"> i; </span><span style="color: rgba(0, 0, 255, 1)">for</span>(i=<span style="color: rgba(128, 0, 128, 1)">1</span>;i&lt;=m;i++<span style="color: rgba(0, 0, 0, 1)">) { cin</span>&gt;&gt;a&gt;&gt;<span style="color: rgba(0, 0, 0, 1)">b; cin</span>&gt;&gt;<span style="color: rgba(0, 0, 0, 1)">tem; u[i] </span>=<span style="color: rgba(0, 0, 0, 1)"> a; v[i] </span>=<span style="color: rgba(0, 0, 0, 1)"> b; edge[i] </span>=<span style="color: rgba(0, 0, 0, 1)"> tem; } kruskal(); </span><span style="color: rgba(0, 0, 255, 1)">return</span> <span style="color: rgba(128, 0, 128, 1)">0</span><span style="color: rgba(0, 0, 0, 1)">; 
 }