Course Schedule – Omówienie zadania – Sortowanie topologiczne

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