.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » wg

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
wg


Timp maxim de execuţie / test:
1.5s
Memorie totala disponibilă / stivă:
32MB / 4MB

Se dă un graf neorientat cu N noduri şi M muchii. Nodurile grafului sunt numerotate cu numere naturale de la 1 la N, iar fiecare nod i are asociat o valoare ai. Fiecare muchie [x, y] a grafului are costul egal cu
min{ai | min(x, y) ≤ imax(x, y)}.

Cerinţă

Scrieţi un program care să determine nodurile unei componente conexe care conţine o muchie de cost maxim. Dacă există mai multe astfel de componente conexe, se cere să se determine componenta conexă care are o muchie de cost maxim incidentă cu un nod cu indice minim.

Date de intrare

Fişierul de intrare wg.in conţine pe prima linie numărul natural N. Pe următoarele N linii sunt date în ordine numerele naturale ai, 1iN. Pe următoarea linie se află numărul natural M. Pe următoarele M linii se află câte două numere naturale x şi y, separate prin spaţiu, reprezentând faptul că există în graf o muchie între nodurile x şi y.

Date de ieşire

Fişierul de ieşire wg.out va conţine pe prima linie costul muchiei de cost maxim în componenta conexă căutată. Pe următoarea linie se va afişa numărul de vârfuri ale componentei conexe şi pe următoarele linii vârfurile componentei conexe în ordine crescătoare, câte unul pe linie.

Restricţii

1N100.000,
1M500.000,
0ai1.000.000.000,
Nu există muchii de la un nod la el însuşi,
Între două noduri există cel mult o muchie.

Exemple

wg.inwg.out
4 6 3 8 3 2 1 2 3 4 3 2 1 2

autor: Prof. Dr. Cornelius Croitoru
propunător: Vlad Manea
Facultatea de Informatică Iași
vlad.c.manea@gmail.com
Articole recomandate
Probleme recomandate
De la FII Competition 2011: lipsa, reducere, viena, sir9, sablon2, fibgcd, acoperire, razboi, safeu, centrala, benzina2, bradut2, capra, agendatelefonica, cds, micro
De acelaşi autor: lipsa, reducere
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, zidar, log, maxq, cover, dist, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, module, nr0, cover1, culori1, flori2, cntgcd, 2sah, matcnt, nmult
Despre LCA: barfa, casute, hacker
surse trimise | ajutor