|
O‘zbekiston respublikasi axborot texnologiyalari vа kommunikatsiyalarini rivojlantirish vazirligi
|
| bet | 3/3 | | Sana | 21.02.2023 | | Hajmi | 0.68 Mb. | | #43065 |
Bog'liq AL Mustaqil ish Botir Tulyaganov 44-20using namespace std;
int p[100000];
int rk[100000];
void init_dsu() {
for (int i = 0; i < 100000; i++) {
p[i] = i;
rk[i] = 1;
}
}
int get_root(int v) {
if (p[v] == v) {
return v;
} else {
return p[v] = get_root(p[v]);
}
}
bool merge(int a, int b) {
int ra = get_root(a), rb = get_root(b);
if (ra == rb) {
return false;
} else {
if (rk[ra] < rk[rb]) {
p[ra] = rb;
} else if (rk[rb] < rk[ra]) {
p[rb] = ra;
} else {
p[ra] = rb;
rk[rb]++;
}
return true;
}
}
struct edge {
int a, b, len;
bool operator<(const edge& other) {
return len < other.len;
}
};
int main() {
vector<edge> edges;
sort(edges.begin(), edges.end());
int mst_weight = 0;
init_dsu();
for (edge e: edges) {
if (merge(e.a, e.b)) {
mst_weight += e.len;
}
}
cout << "Minimum spanning tree weight: " << mst_weight << endl;
}
|
Ish tezligidagi farqlar
Ikkala algoritm ham quyidagilar uchun ishlaydi O(M log N), ularning ishlash tezligida doimiy farqlar mavjud. Kruskal algoritmi siyrak grafikalarda (qirralarning soni taxminan tepaliklar soniga teng) tezroq ishlaydi va to'yingan grafikalarda (qirralarning soni tepaliklar sonining kvadratiga teng) - Prim algoritmi (qo'shni matritsadan foydalanganda).
Amalda Kruskal algoritmi ko'proq qo'llaniladi.
|
| |
