Course Schedule – Omówienie zadania – Sortowanie topologiczne

Szczegółowe omówienie zadania Course Schedule:

Link do powyższego omówienia zadania Course Schedule: https://youtu.be/9IpJXlD6zo8?t=1160
Omówienie kodu zadania Course Schedule: https://youtu.be/9IpJXlD6zo8?t=4298
Link do treści zadania Course Schedule i możliwości umieszczania rozwiązań: https://cses.fi/problemset/task/1679


Zadanie Course Schedule pokazuje sortowanie topologiczne: https://youtu.be/9IpJXlD6zo8?t=1972
Sortowanie topologiczne modeluje nam kolejność czynności przy pomocy grafu skierowanegohttps://youtu.be/9IpJXlD6zo8?t=1471
Warunek na sortowanie topologiczne: https://youtu.be/9IpJXlD6zo8?t=1676
Implementacja sortowania topologicznego: https://youtu.be/9IpJXlD6zo8?t=3582
Złożoność sortowania topologicznego: https://youtu.be/9IpJXlD6zo8?t=3933
Wyjaśnienie sortowania topologicznego w quizie: https://youtu.be/9IpJXlD6zo8?t=6213

Gdzie przydaje się sortowanie topologiczne? https://youtu.be/9IpJXlD6zo8?t=20


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 "Course Schedule", który jest omówiony w powyższym filmie i który otrzymuje 100%


#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
vector<int> G[MAXN];
// liczba krawedzi wchodzacych do wierzcholka
int stopien[MAXN];
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
++stopien[v];
}
vector<int> gotowe;
for (int v = 1; v <= n; ++v) {
if (stopien[v] == 0)
gotowe.push_back(v);
}
vector<int> kolejnosc;
while (!gotowe.empty()) {
int v = gotowe.back();
gotowe.pop_back();
kolejnosc.push_back(v);
for (int i = 0; i < G[v].size(); ++i) {
int u = G[v][i];
--stopien[u];
			if (stopien[u] == 0)
gotowe.push_back(u);
}
}
if (kolejnosc.size() != n) {
cout << "IMPOSSIBLE\n";
}
else {
for (auto v : kolejnosc)
cout << v << ' ';
cout << '\n';
}
return 0;
}
Kod C++ programu "Course Schedule", który jest omówiony w powyższym filmie i który otrzymuje 100%

 


Kod Python programu Course Schedule, który otrzymuje 100%:

def solve():
n, m = map(int, input().split())
G = [[] for i in range(n+1)]
stopien = [0] * (n+1)
for i in range(m):
u, v = map(int, input().split())
G[u].append(v);
stopien[v] += 1
gotowe = []
kolejnosc = []
for v in range(1, n+1):
if (stopien[v] == 0):
gotowe.append(v)
while (len(gotowe) > 0):
v = gotowe.pop()
kolejnosc.append(str(v))
for u in G[v]:
stopien[u] -= 1
if (stopien[u] == 0):
gotowe.append(u)
if (len(kolejnosc) != n):
print("IMPOSSIBLE")
else:
print(' '.join(kolejnosc))
solve()

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz