1118 - Clepsidra

Un graf conex cu N noduri și M muchii poate fi privit ca o clepsidră cu centrul în nodul X, 1 ≤ X ≤ N, dacă putem împărți toate nodurile, mai puțin nodul X, în două submulțimi nevide astfel încât orice drum de la un nod dintr-o mulțime la un nod din cealaltă mulțime trece prin nodul X. Voi trebuie să determinați numărul de moduri distincte în care putem privi graful ca o clepsidră pentru fiecare din cele N noduri alese drept centru, modulo 666013. Două moduri se consideră distincte dacă cele două submulțimi aferente sunt diferite. Ordinea submulțimilor într-un mod este relevantă, dar ordinea nodurilor în cadrul unei mulțimi nu este. Spre exemplu, soluțiile ({1,2,3}, {4,5}) şi ({4,5}, {1,2,3}) sunt distincte, dar soluţiile ({4,5}, {1,2,3}) şi ({4,5}, {1,3,2}) nu sunt distincte.

Date de intrare

Fișierul de intrare clepsidra.in conține pe prima linie două numere naturale, N și M, reprezentând numărul de noduri, respectiv numărul de muchii din graf. Pe următoarele M linii se vor afla câte două numere naturale separate prin câte un spaţiu, reprezentând câte o muchie.

Date de ieșire

Fișierul de ieșire clepsidra.out va conține N linii. A i-a linie, 1 ≤ i ≤ N, va conține numărul de moduri în care putem privi graful ca o clepsidră cu centrul în nodul i, modulo 666013.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 2 ≤ N ≤ 200 002
• 1 ≤ M ≤ 250 002
• Pentru 40% din teste avem restricţiile 2 ≤ N ≤ 1002 și 1 ≤ M ≤ 1502.
• Atentie! Graful este conex.

Exemplul 1:

clepsidra.in

6 7
4 3
1 3
5 4
4 1
3 2
1 5
5 6

clepsidra.out

0
0
2
0
2
0

Explicație

Pentru nodul cu indicele 3, soluţiile sunt: ({2}, {1,4,5,6}) și ({1,4,5,6}, {2})

Pentru nodul cu indicele 5, soluţiile sunt: ({6}, {1,2,3,4}) și ({1,2,3,4},{6})

Exemplul 2:

clepsidra.in

200200 213
4 3
1 3
5 4
4 1
3 2
1 5
5 6

clepsidra.out

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> MOD = 666013

def power(x, y):

   rez = 1
   while y > 0:
       if y % 2 == 1:
           rez = (rez * x) % MOD
       x = (x * x) % MOD
       y = y // 2
   return rez % MOD

def check_constraints(n, m):

   if 2 <= n <= 200002 and 1 <= m <= 250002:
       return True
   else:
       with open("clepsidraOUT.txt", 'w') as out:
           out.write("Datele nu corespund restrictiilor impuse\n")
       return False

def dfs(nc):

   global niv, nmin, nrfii, tati, viz, a, r

   viz[nc] = 1
   niv[nc] = niv[tati[nc]] + 1
   nmin[nc] = niv[nc]
   for nv in a[nc]:
       if viz[nv] == 0:
           tati[nv] = nc
           dfs(nv)
           nmin[nc] = min(nmin[nc], nmin[nv])
           if nc != r and nmin[nv] >= niv[nc]:
               nrfii[nc] += 1

       elif tati[nc] != nv:
           nmin[nc] = min(nmin[nc], niv[nv])

def main():

   global niv, nmin, nrfii, tati, viz, a, r

   with open("clepsidraIN.txt", 'r') as f:
       n, m = map(int, f.readline().split())
       
       if not check_constraints(n, m):
           return
       
       a = [[] for _ in range(n + 1)]
       for _ in range(m):
           x, y = map(int, f.readline().split())
           a[x].append(y)
           a[y].append(x)

   r = 1
   niv = [0] * (n + 1)
   nmin = [0] * (n + 1)
   nrfii = [0] * (n + 1)
   tati = [0] * (n + 1)
   viz = [0] * (n + 1)

   dfs(r)

   with open("clepsidraOUT.txt", 'w') as out:
       if nrfii[r] > 1:
           out.write(str((power(2, nrfii[r]) + MOD - 2) % MOD) + "\n")
       else:
           out.write("0\n")

       for i in range(2, n + 1):
           if nrfii[i] == 0:
               out.write("0\n")
           else:
               out.write(str((power(2, nrfii[i] + 1) + MOD - 2) % MOD) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>