MST

Kruskal.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> parent, rnk;

void make_set(int v) {
    parent[v] = v;
    rnk[v] = 0;
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rnk[a] < rnk[b])
            swap(a, b);
        parent[b] = a;
        if (rnk[a] == rnk[b])
            rnk[a]++;
    }
}

struct Edge{
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};

int main() {
    int n; cin >> n;
    int m; cin >> m;
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++)
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
    int cost = 0;
    vector<Edge> result;
    parent.resize(n);
    rnk.resize(n);
    for (int i = 0; i < n; i++)
        make_set(i);
    sort(edges.begin(), edges.end());
    for (Edge e : edges) {
        if (find_set(e.u) != find_set(e.v)) {
            cost += e.weight;
            result.push_back(e);
            union_sets(e.u, e.v);
        }
    }

    cout << "Minimum Cost: " << cost << endl;
    cout << "Edges in MST:\n";
    for (Edge e : result) {
        cout << e.u << " - " << e.v << " = " << e.weight << endl;
    }
}

primsMST.cpp

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

const int INF = 1000000000;

int n, x, m; 

vector<vector<int>> adj; 

struct Edge {
    int w = INF, to = -1;
};

void prim() {
    int total_weight = 0;
    vector<bool> selected(n, false);
    vector<Edge> min_e(n);
    min_e[x].w = 0;

    for (int i = 0; i < n; ++i) {
        int v = -1;
        for (int j = 0; j < n; ++j) {
            if (!selected[j] && (v == -1 || min_e[j].w < min_e[v].w))
                v = j;
        }

        if (min_e[v].w == INF) {
            cout << "No MST!" << endl;
            exit(0);
        }

        selected[v] = true;
        total_weight += min_e[v].w;
        if (min_e[v].to != -1)
            cout << v << " " << min_e[v].to << endl;

        for (int to = 0; to < n; ++to) {
            if (adj[v][to] < min_e[to].w && !selected[to]) {
                min_e[to] = {adj[v][to], v};
            }
        }
    }

    cout << "Total weight of MST: " << total_weight << endl;
}

int main() {
    cin >> n >> m;
    cout << "Starting Vertex : ";
    cin >> x;
    adj.assign(n, vector<int>(n, INF));

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u][v] = w;
        adj[v][u] = w; 
    }

    prim();

    return 0;
}

quicksort.cpp

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int partition(vector<int> &arr, int low, int high) {
    int pivot = arr[low];
    int left = low;

    for (int i = low + 1; i <= high; i++) {
        if (arr[i] < pivot) {
            swap(arr[i], arr[left++]);
        }
    }
    swap(arr[low], arr[left - 1]);
    return left;
}

void quicksort(vector<int> &arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quicksort(arr, low, pivot-1);
        quicksort(arr, pivot + 1, high);
    }
}

int main() {
    vector<int> arr = {11, 2, 33, 45, 15};
    quicksort(arr, 0, arr.size()-1);
    for (auto i : arr) cout << i << " ";
}