Jittat: สร้างหน้าด้วย "== Slow kruskal == #include #include #include using namespace std; const int MAX_N = 10001..."

2026-02-23T07:09:42Z

สร้างหน้าด้วย "== Slow kruskal == <syntaxhighlight lang="cpp"> #include <iostream> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 10001..."

หน้าใหม่

== Slow kruskal ==

<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX_N = 100010;
const int MAX_M = 200010;

int n,m;
pair<int,int> edges[MAX_M];
int weights[MAX_M];
vector<pair<int,int>> windex;

void read_input()
{
cin >> n >> m;
for(int i=0; i<m; i++) {
int u,v,l;
cin >> u >> v >> l; u--; v--;
edges[i].first = u;
edges[i].second = v;
weights[i] = l;

// for sorting
windex.push_back({ l, i });
}
sort(windex.begin(), windex.end());
}

int components[MAX_N];
void init_union_find()
{
for(int i=0; i<n; i++)
components[i] = i;
}
int find(int u)
{
return components[u];
}
void union_sets(int cu, int cv)
{
if(cu == cv)
return;
for(int i=0; i<n; i++)
if(components[i] == cu)
components[i] = cv;
}

int main()
{
read_input();
int cost = 0;
init_union_find();
for(int i=0; i<m; i++) {
// consider windex[i] -- edge with the i-th min weight
int e = windex[i].second;
int l = weights[e];
int u = edges[e].first;
int v = edges[e].second;

int cu = find(u);
int cv = find(v);
if(cu != cv) {
cost += l;
union_sets(cu,cv);
}
}
cout << cost << endl;
return 0;
}
</syntaxhighlight>

== Milk ==

<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;
const int MAX_N = 100010;
const int MAX_M = 200010;

int n,q;

int parents[MAX_N];
int s[MAX_N];

void init_union_find()
{
for(int i=0; i<n; i++) {
parents[i] = i;
s[i] = 1;
}
}
int find(int u)
{
if(parents[u] == u) // I'm groot
return u;
else
return find(parents[u]);
}
void union_sets(int cu, int cv)
{
assert(parents[cu] == cu);
assert(parents[cv] == cv);
if(cu == cv)
return;
if(s[cu] > s[cv]) {
// ... TODO
} else {
// ... TODO
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);

char cmd[10];
cin >> n >> q;
init_union_find();
for(int i=0; i<q; i++) {
int x, y;
cin >> cmd >> x >> y; x--; y--;

int cx = find(x);
int cy = find(y);
if(cmd[0] == 'c') {
union_sets(cx,cy);
} else {
if(cx == cy)
cout << "yes\n";
else
cout << "no\n";
}
}
return 0;
}
</syntaxhighlight>

Kruskal union find - ประวัติรุ่นแก้ไข

Jittat: สร้างหน้าด้วย "== Slow kruskal == #include #include #include using namespace std; const int MAX_N = 10001..."