Editing 1118 - Clepsidra


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>