Stumilowa Puszcza – Omówienie zadania – Jak przechowywać grafy?

Szczegółowe omówienie zadania Stumilowa puszcza:

Link do powyższego omówienia zadania Stumilowa puszcza: https://youtu.be/NDp4nZnqtEo?t=1325
Omówienie kodu zadania Stumilowa puszcza: https://youtu.be/NDp4nZnqtEo?t=3526

Link do treści zadania Stumilowa puszcza i możliwości umieszczania rozwiązań:
https://szkopul.edu.pl/problemset/problem/stu/site

Zadanie Stumilowa puszcza pokazuje czym są grafy? https://youtu.be/NDp4nZnqtEo?t=297
Jak przechowywać grafy: https://youtu.be/NDp4nZnqtEo?t=1824
Jak zaimplementować graf w C++/Python? https://youtu.be/NDp4nZnqtEo?t=2470
Jaka jest złożoność wczytywania / wypisywania grafu? https://youtu.be/NDp4nZnqtEo?t=3219
Graf – kod/implementacja w C++
https://youtu.be/NDp4nZnqtEo?t=3536


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/

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


Kod C++ programu Stumilowa Puszcza, który jest omówiony w powyższym filmie i który otrzymuje 100%


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

const int MAXN = 5e5 + 7;

// Graf, reprezentowany jako lista sąsiedztwa
vector<int> G[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 p, q;
		cin >> p >> q;
		// p jest sąsiadem q oraz odwrotnie
		G[p].push_back(q);
		G[q].push_back(p);
	}

	for (int i = 1; i <= n; ++i) {
		// G[i] - vector zawierający sąsiadów wiewiórki i
		if (G[i].empty()) {
			cout << "Wiewior sam!\n";
		}
		else {
			sort(G[i].begin(), G[i].end());
			for (size_t j = 0; j < G[i].size(); ++j)
				cout << G[i][j] << ' '; // wypisujemy j-ty element w vectorze G[i]
			cout << '\n';
		}
	}
	return 0;
}
Kod C++ programu Stumilowa Puszcza, który jest omówiony w powyższym filmie i który otrzymuje 100%

 


Kod Python programu Stumilowa puszcza, który otrzymuje 100%:

from sys import stdin
input = stdin.readline

def solve():
	n, m = map(int, input().split())
	G = [[] for i in range(n + 1)]
	for i in range(m):
		p, q = map(int, input().split())
		G[p].append(q)
		G[q].append(p)

	for v in range(1, n + 1):
		if (len(G[v]) == 0):
			print("Wiewior sam!")
		else:
			for u in sorted(G[v]):
				print(u, end = ' ')
			print()

solve()

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz