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

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


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

Se dă un graf neorientat cu N noduri (numerotate de la 1 la N) şi M muchii. Vom defini A(i,j)=1 dacă nodurile i şi j sunt adiacente (există o muchie între ele), respectiv A(i,j)=0 dacă nodurile i şi j nu sunt adiacente.
O submulţime S de noduri ale grafului se numeşte modul dacă îndeplineşte următoarea condiţie:

Oricare ar fi trei noduri x, y şi z astfel încât x aparţine lui S, y aparţine lui S şi z nu aparţine lui S, avem A(x,z)=A(y,z).

Mai exact, pentru orice nod z din afara mulţimii S, ori toate nodurile din S sunt adiacente cu z, ori niciun nod din S nu este adiacent cu z. Câteva exemple simple de module sunt: mulţimea vidă, mulţimea tuturor nodurilor grafului, mulţimile ce constau din câte un singur nod al grafului.

Cerinţă

Determinaţi numărul de module ale grafului dat, modulo 34949.

Date de intrare

Prima linie a fişierului de intrare module.in conţine numerele întregi N şi M, separate printr-un spaţiu. Următoarele M linii conţin câte două numere întregi i j, separate printr-un spaţiu, având semnificaţia că există o muchie între nodul i şi nodul j în graf.

Date de ieşire

În fişierul de ieşire module.out veţi afişa numărul de module ale grafului dat, modulo 34949.

Restricţii

• 1 ≤ N ≤ 100
• 0 ≤ M ≤ N∙(N-1)/2
• 1 ≤ i,j ≤ N
• i ≠ j
În fişierul de intrare nu se vor repeta muchii.

Exemple

module.inmodule.outExplicaţii
7 11 5 1 5 6 1 2 1 3 1 7 6 2 6 3 6 7 4 2 4 3 4 7 14 Cele 14 module sunt:
{}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {1,6}, {2,3}, {2,7}, {3,7}, {2,3,7}, {1,2,3,4,5,6,7}.


autor: Mugurel Ionuţ Andreica
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la LOT AR 2011: acoperire1, joc19, minusk, radioactiv, triburi, robot4, 3max, mofocarburi
De acelaşi autor: autobuze, bile, complex, balaur, vmem, kreg, ro, jobs, senzori, echipe, agitatie, center, algebra, tgraf, bcast, promo, asmax, sediu, granita, string, poligon1, csir, lsort, zoo, bombo, ab3, soc, rsp, tcast, tj, lanterna, base3, color, trans, ic, xp, v2d, ppcover, carray, asfalt1, gxor
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, wg, neconex, asfalt1, kubus2, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre combinatorică: manevre, carti, bonuri, test, cub, nspecial, circuit, numere, cs, pluricex, parent, gray, siruri, anagrame, party, net, scaune, sir, monede, aztec, nrcuv2, perm, race, hanoig, red, grup, hperm, depou, grazing, pm, reteta2, playlist, young, pizza1, albine, caramele, teatru1, tub, robot1, sir23, soldati1, concurs1, comb, expresii, arbnr, cod1, munte, shgraf, desc, lex, munte1, maxperm, role, avere, vizibil, prime1, hexa, patrat, carti2, puncte2, pact, aranjari, numere5, borg, acolor, sg1, perfect, cifru2, bile4, pviz, culmi1, piramida1, trapez, frunze, sir7, logic, coduri, jetoane, kperms, tablite, secvpar, lego, permutari, binperm, multiplu1, operatii, fotbal, kbiti, jucarii, bradut, expozitie, parbit, kmax, petrecere, tango, rege, cd1, cifru3, kcons, bubblesort, hawaii, randomizare, kdist, reuniune, echipa, ghinion, cavaleri, camera616, covor, subm, grupuri, pavari, asfalt, adunscad, rotund, sport2, arbore1, lant1, nrperm, oneton, nrpomi, cover1, nrpal, probleme, optim, poly, vot1, sudoku1, flori2, xnumere, showroom, cntgcd, subsets, nkd, nrgraf, spion1, puteri, stiva1, permtr, relatii, 2sah, matcnt, magic7, nmult, roua
Despre conexitate: arce, flood, matrice, shgraf, trip, pact, echipe1, vitale, spion, bcolor, mexc, dep, fazan, cfr, chei, teme, entries, pamant, neconex, drumuri2, cristal, 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, wg, nr0, cover1, culori1, 2ndesc, flori2, cntgcd, 2sah, matcnt, nmult
surse trimise | ajutor