20 anys del Jutge.org

El Professor Oak està de celebració. Enguany, el Jutge.org, la pàgina
web més estimada de tota la comunitat UPC, fa 20 anys. Sí, 20 anys
enrere el Professor Oak i el Professor Small van crear aquesta
plataforma.

El Professor Oak ha quedat molt satisfet de la festa d’aniversari. Hi ha
dominat la Coca-Cola, els dònuts, les galetes i altres queviures de
qüestionables propietats alimentícies, però també la felicitat per tots
aquests anys i el desig perquè el Jutge.org segueixi endavant per molts
anys més sense quedar plena de AI slop com la resta de l’Internet.

Ara bé, el Professor Oak encara té ganes per més. Com que no hi ha res
que els estudiants de la FME estimin més que resoldre problemes
d’algorísmia, el Professor Oak organitzarà un concurs improvisat a la
FME. Desgraciadament, els ordinadors de les aules d’informàtica tenen un
comportament ben curiós. Aquesta vegada, no es poden connectar a
Internet, però sí que alguns d’ells es poden comunicar entre si, formant
una mena de múltiples xarxes locals d’ordinadors. Per estalviar temps,
el servei tècnic de la FME ha decidit connectar a la xarxa directament
només uns pocs ordinadors, concretament un ordinador per cadascuna
d’aquestes xarxes locals, de manera que actuï com a router per a la
resta d’ordinadors de la seva xarxa. El servei tècnic necessita saber
quantes connexions haurà de realitzar.

Podeu ajudar-los per tal que el Professor Oak pugui organitzar el seu
concurs?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre
d’ordinadors n i el nombre de connexions entre ordinadors m. Després,
segueixen m parells d’enters x, y que indiquen que l’ordinador x i
l’ordinador y estan connectats.

Podeu suposar que 1 <  = n <  = 10⁴, 0 <  = m <  = 5n, que els
ordinadors es numeren de 0 a n − 1 i que no hi ha més de dues connexions
entre dos mateixos ordinadors x, y.

Sortida

Per cada cas, digueu quantes xarxes locals d’ordinadors hi ha (i.e.
conjunts d’ordinadors que estan connectats entre si i no amb cap altre
ordinador).

Pista

Feu una cerca en profunditat.

Informació del problema

Autoria: Àlex Touza

Generació: 2026-07-16T23:03:52.047Z

© Jutge.org, 2006–2026.
https://jutge.org
