Rezumat problemă

esentiale

#4950

Fie G un graf neorientat conex cu N noduri și M muchii. Nodurile sunt numerotate de la 1 la N iar muchiile au asociate costuri numere naturale date. Un graf parţial al lui G conex şi fără cicluri este denumit arbore parţial. Costul unui arbore parțial este suma costurilor muchiilor arborelui. Deoarece unele muchii pot avea aceelași cost, este posibil ca graful G să aibă mai mulți arbori parțiali de cost minim. Definim o muchie a grafului G ca fiind esențială dacă ea face parte din toți arborii parțiali de cost minim ai lui G. Scrieţi un program care, cunoscând graful, rezolvă următoarele două cerinţe:
1. determină costul unui arbore parțial de cost minim al lui G;
2. determină numărul de muchii esențiale ale grafului G.

OMI 2026, clasele 11-12

Fișiere Pracsiu Dan (dnprx) Paul Diac concurs

Clasa 11 Teoria Grafurilor Grafuri cu costuri Algoritmul lui Kruskal

Rezolvă

Detalii

Problema	esentiale	Operații I/O	esentiale.in/esentiale.out
Limita timp	0.5 secunde	Limita memorie	Total: 64 MB / Stivă 16 MB
Id soluție	#64617860	Utilizator	David Ionescu (IonescuDavidGabriel)
Fișier	esentiale.cpp	Dimensiune	3.03 KB
Data încărcării	18 Mai 2026, 20:47	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

esentiale.cpp:5:1: error: expected ‘,’ or ‘;’ before ‘int’
    5 | int const NMAX=1000;
      | ^~~
esentiale.cpp:6:10: error: ‘NMAX’ was not declared in this scope
    6 | int tata[NMAX]; // tata[i] = parintele lui i in arbore
      |          ^~~~
esentiale.cpp:7:10: error: ‘NMAX’ was not declared in this scope
    7 | int rang[NMAX]; // adancimea aproximativa a subarborelui
      |          ^~~~
esentiale.cpp:8:9: error: ‘NMAX’ was not declared in this scope
    8 | int dim[NMAX];  // dimensiunea componentei (alternativ la rang)
      |         ^~~~
esentiale.cpp: In function ‘void init_dsu(int)’:
esentiale.cpp:11:9: error: ‘tata’ was not declared in this scope
   11 |         tata[i] = i;  // fiecare element e propria sa radacina
      |         ^~~~
esentiale.cpp:12:9: error: ‘rang’ was not declared in this scope; did you mean ‘rand’?
   12 |         rang[i] = 0;
      |         ^~~~
      |         rand
esentiale.cpp:13:9: error: ‘dim’ was not declared in this scope; did you mean ‘fdim’?
   13 |         dim[i] = 1;
      |         ^~~
      |         fdim
esentiale.cpp: In function ‘int find(int)’:
esentiale.cpp:19:9: error: ‘tata’ was not declared in this scope
   19 |     if (tata[x] != x)
      |         ^~~~
esentiale.cpp:21:12: error: ‘tata’ was not declared in this scope
   21 |     return tata[x];
      |            ^~~~
esentiale.cpp: In function ‘bool unite(int, int)’:
esentiale.cpp:32:9: error: ‘rang’ was not declared in this scope; did you mean ‘rand’?
   32 |     if (rang[x] < rang[y]) swap(x, y);
      |         ^~~~
      |         rand
esentiale.cpp:33:5: error: ‘tata’ was not declared in this scope
   33 |     tata[y] = x;       // y devine copilul lui x
      |     ^~~~
esentiale.cpp:34:5: error: ‘dim’ was not declared in this scope; did you mean ‘fdim’?
   34 |     dim[x] += dim[y];  // actualizeaza dimensiunea
      |     ^~~
      |     fdim
esentiale.cpp:35:9: error: ‘rang’ was not declared in this scope; did you mean ‘rand’?
   35 |     if (rang[x] == rang[y]) rang[x]++;
      |         ^~~~
      |         rand
esentiale.cpp: In function ‘long long int kruskal(int, std::vector<Muchie>&)’:
esentiale.cpp:74:16: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   74 |     for (auto& [u, v, cost] : muchii) {
      |                ^
esentiale.cpp: In function ‘int main()’:
esentiale.cpp:96:20: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   96 |         for (auto& [cost, lista] : muchii_mst) {
      |                    ^

Cum funcționează evaluarea?