Rus Marius: Pagină nouă: 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 cle...

2024-01-06T21:26:53Z

Pagină nouă: Un graf conex cu <code>N</code> noduri și <code>M</code> muchii poate fi privit ca o clepsidră cu centrul în nodul <code>X</code>, <code>1 ≤ X ≤ N</code>, dacă putem împărți toate nodurile, mai puțin nodul <code>X</code>, î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 <code>X</code>. Voi trebuie să determinați numărul de moduri distincte în care putem privi graful ca o cle...

New page

Un graf conex cu <code>N</code> noduri și <code>M</code> muchii poate fi privit ca o clepsidră cu centrul în nodul <code>X</code>, <code>1 ≤ X ≤ N</code>, dacă putem împărți toate nodurile, mai puțin nodul <code>X</code>, î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 <code>X</code>. Voi trebuie să determinați numărul de moduri distincte în care putem privi graful ca o clepsidră pentru fiecare din cele <code>N</code> noduri alese drept centru, modulo <code>666013</code>. 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 <code>({1,2,3}, {4,5})</code> şi <code>({4,5}, {1,2,3})</code> sunt distincte, dar soluţiile <code>({4,5}, {1,2,3})</code> şi <code>({4,5}, {1,3,2})</code> nu sunt distincte.

= Date de intrare =
Fișierul de intrare <code>clepsidra.in</code> conține pe prima linie două numere naturale, <code>N</code> și <code>M</code>, reprezentând numărul de noduri, respectiv numărul de muchii din graf. Pe următoarele <code>M</code> 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 <code>clepsidra.out</code> va conține <code>N</code> linii. A <code>i</code>-a linie, <code>1 ≤ i ≤ N</code>, va conține numărul de moduri în care putem privi graful ca o clepsidră cu centrul în nodul <code>i</code>, modulo <code>666013</code>.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

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

= Exemplul 1: =
<code>clepsidra.in</code>
6 7
4 3
1 3
5 4
4 1
3 2
1 5
5 6
<code>clepsidra.out</code>
0
0
2
0
2
0

= Explicație =
Pentru nodul cu indicele <code>3</code>, soluţiile sunt: <code>({2}, {1,4,5,6})</code> și <code>({1,4,5,6}, {2})</code>

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

== Exemplul 2: ==
<code>clepsidra.in</code>
200200 213
4 3
1 3
5 4
4 1
3 2
1 5
5 6
<code>clepsidra.out</code>
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>

1118 - Clepsidra - Revision history