https://theory.cpe.ku.ac.th/wiki/index.php?action=history&feed=atom&title=Psl%2Fkruskal 2026-04-22T11:07:25Z ประวัติรุ่นแก้ไขของหน้านี้ในวิกิ MediaWiki 1.33.1 https://theory.cpe.ku.ac.th/wiki/index.php?title=Psl/kruskal&diff=59496&oldid=prev 2024-01-29T07:15:52Z

<p>สร้างหน้าด้วย &quot;&lt;syntaxhighlight lang=&quot;cpp&quot;&gt; #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;set&gt; #include &lt;algorithm&gt; using namespace std; const int MAX_N = 100010;...&quot;</p> <p><b>หน้าใหม่</b></p><div>&lt;syntaxhighlight lang=&quot;cpp&quot;&gt;<br /> #include &lt;iostream&gt;<br /> #include &lt;vector&gt;<br /> #include &lt;set&gt;<br /> #include &lt;algorithm&gt;<br /> <br /> using namespace std;<br /> <br /> const int MAX_N = 100010;<br /> <br /> int n,m;<br /> vector&lt;int&gt; adj[MAX_N];<br /> vector&lt;int&gt; weights[MAX_N];<br /> <br /> vector&lt;pair&lt;int,int&gt;&gt; edges;<br /> vector&lt;int&gt; edge_weights;<br /> <br /> int deg[MAX_N];<br /> <br /> set&lt;pair&lt;int,int&gt;&gt; Q;<br /> <br /> vector&lt;pair&lt;int,int&gt;&gt; sedges;<br /> <br /> void read_input()<br /> {<br /> cin &gt;&gt; n &gt;&gt; m;<br /> for(int u=0; u&lt;n; u++) deg[u] = 0;<br /> for(int i=0; i&lt;m; i++) {<br /> int a,b,w;<br /> cin &gt;&gt; a &gt;&gt; b &gt;&gt; w; a--; b--;<br /> adj[a].push_back(b);<br /> adj[b].push_back(a);<br /> weights[a].push_back(w);<br /> weights[b].push_back(w);<br /> deg[a]++;<br /> deg[b]++;<br /> <br /> edges.push_back(make_pair(a,b));<br /> edge_weights.push_back(w);<br /> <br /> sedges.push_back(make_pair(w,i));<br /> }<br /> }<br /> <br /> /*<br /> int set_number[MAX_N];<br /> <br /> void init_set()<br /> {<br /> for(int i=0; i&lt;n; i++)<br /> set_number[i] = i;<br /> }<br /> <br /> int set_find(int u)<br /> {<br /> return set_number[u];<br /> }<br /> <br /> void set_union(int pu, int pv)<br /> {<br /> for(int i=0; i&lt;n; i++)<br /> if(set_number[i] == pu)<br /> set_number[i] = pv;<br /> }<br /> */<br /> <br /> int set_parent[MAX_N];<br /> int set_rank[MAX_N];<br /> <br /> void init_set()<br /> {<br /> for(int i=0; i&lt;n; i++) {<br /> set_parent[i] = i;<br /> set_rank[i] = 1;<br /> }<br /> }<br /> <br /> int set_find(int u)<br /> {<br /> if(set_parent[u] == u) {<br /> return u;<br /> } else {<br /> return set_find(set_parent[u]);<br /> }<br /> }<br /> <br /> void set_union(int pu, int pv)<br /> {<br /> pu = set_find(pu);<br /> pv = set_find(pv);<br /> if(pu == pv)<br /> return;<br /> if(set_rank[pv] &gt; set_rank[pu]) {<br /> set_parent[pu] = pv;<br /> } else if(set_rank[pu] &gt; set_rank[pv]) {<br /> set_parent[pv] = pu;<br /> } else {<br /> set_parent[pv] = pu;<br /> set_rank[pu]++;<br /> }<br /> }<br /> <br /> main()<br /> {<br /> int total = 0;<br /> read_input();<br /> init_set();<br /> sort(sedges.begin(), sedges.end());<br /> for(int i=0; i&lt;m; i++) {<br /> int e = sedges[i].second;<br /> int u = edges[e].first;<br /> int v = edges[e].second;<br /> int w = edge_weights[e];<br /> <br /> int pu = set_find(u);<br /> int pv = set_find(v);<br /> if(pu != pv) {<br /> total += w;<br /> set_union(pu,pv);<br /> }<br /> }<br /> cout &lt;&lt; total &lt;&lt; endl;<br /> }<br /> <br /> &lt;/syntaxhighlight&gt;</div>

Jittat