Fişierul intrare/ieşire:module.in, module.outSursăLot Arad 2011
AutorMugurel Ionut AndreicaAdăugată deandrei.12Andrei Parvu andrei.12
Timp execuţie pe test1.05 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Module

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 si z astfel incat x ∈ S, y ∈ S si z ∉ 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.
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 ş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.

Exemplu

module.inmodule.out
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

Explicaţie

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}.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content