Szczegółowe omówienie zadania Min Cost to Connect All Points:

Link do powyższego omówienia zadania Min Cost to Connect All Points: https://youtu.be/jOqGMOGJQ1s?t=1117
Omówienie kodu który zadania Min Cost to Connect All Points: https://youtu.be/jOqGMOGJQ1s?t=4744

Link do treści zadania Min Cost to Connect All Points i możliwości umieszczania rozwiązań: https://leetcode.com/problems/min-cost-to-connect-all-points/

–
Zadanie pokazuje algorytm Find And Union: https://youtu.be/jOqGMOGJQ1s?t=2036

–
Zadanie z LeetCode – platformy która zawiera zadania z interview / rozmów kwalifikacyjnych do Google, Facebook, Amazon: https://youtu.be/jOqGMOGJQ1s?t=17

–
Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/

Zajęcia: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109

–
Kod C++ programu "Min Cost to Connect All Points", który jest omówiony w powyższym filmie i który otrzymuje 100%

–

class Solution {
public:
	int rep[1007];

	int Find(int v) {
		if (rep[v] != v)
			rep[v] = Find(rep[v]);
		return rep[v];
	}

	void Union(int u, int v) {
		int a = Find(u);
		int b = Find(v);
		rep[a] = b;
	}

	int minCostConnectPoints(vector<vector<int>>& points) {
		vector<pair<int, pair<int, int>>> kraw;
		for (int i = 0; i < points.size(); ++i) {
			for (int j = i + 1; j < points.size(); ++j) {
				int d = abs(points[i][0] - points[j][0])
						+ abs(points[i][1] - points[j][1]);
				kraw.push_back({d, {i, j}});
			}
		}
		sort(kraw.begin(), kraw.end());
		for (int i = 0; i < points.size(); ++i)
			rep[i] = i;
		int wynik = 0;
		for (int i = 0; i < kraw.size(); ++i) {
			int d = kraw[i].first;
			int u = kraw[i].second.first;
			int v = kraw[i].second.second;
			if (Find(u) != Find(v)) {
				wynik += d;
				Union(u, v);
			}
		}
		return wynik;
	}
};

–
Kod Python programu Min Cost to Connect All Points, który otrzymuje 100%:

class Solution:
    rep = []
    def Find(self, v):
        if (self.rep[v] != v):
            self.rep[v] = self.Find(self.rep[v])
        return self.rep[v]

    def Union(self, u, v):
        a = self.Find(u)
        b = self.Find(v)
        self.rep[a] = b

    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        self.rep = [i for i in range(len(points))]
        kraw = []
        for i in range(len(points)):
            for j in range(i+1, len(points)):
                d = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                kraw.append([d, i, j])
        kraw.sort()
        wynik = 0
        for d, u, v in kraw:
            if (self.Find(u) != self.Find(v)):
                wynik += d
                self.Union(u, v)
        return wynik