Acest site foloseşte cookies. Navigând în continuare, vă exprimaţi acordul asupra folosirii cookie-urilor.

Lista de probleme 10

Filtrare

Mai multe opțiuni

#438 ComponenteConexe

Se dă lista muchiilor unui graf neorientat. Să se afișeze componentele conexe ale acestui graf.

Rezolvă

#441 ComponenteConexe1

Se dă lista muchiilor unui graf neorientat. Să se determine numărul minim de muchii care trebuie adăugate pentru ca graful să devină conex, precum și un set de asemenea muchii.

Rezolvă

#537 ComponenteConexe2

Se dă lista muchiilor unui graf neorientat. Să se determine numărul de muchii care pot fi eliminate din graf astfel încât numărul de componente conexe ale grafului să nu se modifice.

Rezolvă

#1603 ComponenteConexe3

Se dă lista muchiilor unui graf neorientat. Pentru fiecare componentă conexă numim cel mai mic vârf de ea reprezentant al componentei conexe. Determinați reprezentantul componentei conexe cu cele mai multe vârfuri și câte noduri conține aceasta.

Rezolvă

#2282 ComponenteConexe4

Se consideră un graf neorientat cu n vârfuri și m muchii. Cele m muchii se elimină pe rând din graf. Pentru fiecare muchie eliminată trebuie să spuneți câte componente conexe are graful.

Rezolvă

#3364 Unire

Gigel are un graf cu n noduri și m muchii, care nu este conex. El dorește să afle răspunsul la două întrebări:

1) Care este numărul minim de muchii ce trebuie ađugate astfel încât graful să devină conex?
2) Dacă costul adăugării unei muchii între nodurile a și b este a + b, care este costul total minim al muchiilor care trebuie adăugate astfel încât graful să devină conex?

Rezolvă

#1497 Nunta

La o nuntă sunt invitate n persoane, numerotate de la 1 la n. Se știe că o parte din ele se cunosc două câte două, fie că sunt rude, fie de la serviciu, fie sunt prieteni sau vecini. Astfel se vor forma un număr K minim de grupuri astfel încât în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut. Pentru fiecare grup de cel puțin două persoane se stabileşte un lider – persoana cu numărul de ordine minim. Aceste grupuri vor fi numerotate de la 1 la K în ordinea crescătoare a numerelor de ordine ale liderilor. Ca sa se ivească cât mai puține situații stânjenitoare, organizatorul nunții ar dori să aranjeze o masă principală cu cel puţin n/2+1 invitaţi, la care să fie aşezate unul sau mai multe astfel de grupuri întregi numerotate cu valori consecutive.

Fiind date n, numărul de persoane, m, numărul de perechi de invitaţi care se cunosc între ei și cele m perechi, să se determine numărul minim de grupuri formate din cel puțin doi invitați astfel încât, în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut, precum şi numărul variantelor distincte în care se poate organiza masa cu cel puţin n/2+1 invitaţi din grupurile formate.

Olimpiada locală de Informatică, Prahova, 2016

Rezolvă

#3235 entries

Se consideră un graf care inițial este format din P noduri izolate, etichetate de la 1 la P. Se mai consideră N intrări, unde intrare poate însemna:

  • comandă – o comandă are forma I + J, cu semnificația că în graf se adaugă muchia care unește nodurile I și J (dacă I și J erau deja unite în acel moment, nu se întreprinde nici o acțiune);
  • întrebare – o întrebare este de forma I ? J, adică se întreabă dacă în acel moment I și J sunt în aceeași componentă conexă.

Se pleacă deci de la un graf inițial format din noduri izolate, care pe parcurs se “unifică”. Tot pe parcurs sunteți întrebat dacă anumite perechi de noduri sunt sau nu în aceeași componentă conexă. Scrieți un program care să răspundă la întrebările din fișierul de intrare.

ONI 2001, clasele XI-XII

Rezolvă

#2514 warcraft

Durotan, căpetenia clanului Frostwolf, face o ultima încercare în a cuceri clanurile rivale (Orcish Horde). Conform ierarhiei Orcish, căpeteniile de clan sunt denumite warchief, în timp ce liderii triburilor sunt denumiți șamani. Triburile din care fac parte căpeteniile sunt triburi dominante, iar triburile conduse de șamani sunt triburi vasale. Pe planetă există N triburi, numerotate de la 1 la N. Șamanul unui trib are anumite abilități de luptă. Căpetenia unui clan este șamanul tribului său. Abilitățile de luptă cunoscute de șamani sunt numerotate de la 1 la M. De-a lungul timpului între triburile aceluiași clan s-au stabilit relații de vasalitate. Dacă tribul 1 este trib dominant al tribului vasal 2, iar tribul 2 are ca vasal tribul 3, vom spune că tribul 3 se află în zona de influență a triburilor 1 și 2. Triburile 1,2,3 alcătuiesc un clan. Puterea unei căpetenii depinde de numărul triburilor ce alcătuiesc clanul, precum și de abilitățile de luptă învățate. Căpetenia unui clan are anumite abilități de luptă, dar poate să-și însușească (învețe) și abilități de luptă unice de la șamanii triburilor clanului aflate în zona sa de influență. Prin abilități de luptă unice înțelegem abilități cunoscute doar de un singur șaman din totalitatea triburilor clanului. Fiind cunoscute pentru cele N triburi abilitățile fiecărui șaman, relațiile de vasalitate între triburi, numărul de ordine al unui trib al clanului Frostwolf, să se determine:
  • numărul total de clanuri
  • numărul de triburi din clanul Frostwolf înainte de duel
  • numărul maxim de triburi pe care Duroton le poate avea după invocarea codului Mak’gora.

Lot juniori Câmpulung Muscel, 2018

Rezolvă

#2968 conexidad

Fie un graf neorientat cu N noduri și M muchii, care NU este conex. Să i se adauge grafului un număr minim de muchii, astfel încât acesta să devină conex. Fie extrai numărul de muchii nou-adăugate care sunt incidente cu nodul i, iar max_extra cea mai mare dintre valorile extra1, extra2,… , extraN. Mulțimea de muchii adăugate trebuie să respecte condiția ca valoarea max_extra să fie minimă.

OJI 2019

Rezolvă