Editing 0544 - Partial

= Cerința =
Se dă un graf neorientat conex cu <code>n</code> vârfuri și număr par de muchii. Să se determine un graf parțial al celui dat care să fie conex și să fie obținut prin eliminarea a jumătate din numărul de muchii.

= Date de intrare =
Fișierul de intrare <code>partialIN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe a următoarele linii perechi de numere <code>i j</code>, cu semnificația că există muchie de la <code>i</code> la <code>j</code>.

= Date de ieșire =
Fișierul de ieșire <code>partialOUT.txt</code> va conține matricea de adiacență a grafului parțial obținut, câte o linie a matricei pe o linie a fișierului, elementele fiecărei linii fiind separate prin exact un spațiu.Î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>1 ≤ n ≤ 200</code>
* <code>1 ≤ i,j ≤ n</code>
* se garantează existența unui graf parțial cu proprietatea cerută

= Exemplul 1: =
<code>partialIN.txt</code>
 6
 1 2
 1 3
 1 4
 1 5
 1 6
 2 4
 2 5
 3 4
 3 5
 4 5
 4 6
 5 6
<code>partialOUT.txt</code>
 0 1 0 0 0 0 
 1 0 0 1 0 0 
 0 0 0 1 1 0 
 0 1 1 0 0 1 
 0 0 1 0 0 1 
 0 0 0 1 1 0 

= Observații =

* 2016, iunie 02: am adăugat un test cu o situație care nu era cuprinsă în testele anterioare.

== Exemplul 2: ==
<code>partialIN.txt</code>
 201
 1 2
 1 3
 1 4
 1 5
 1 6
 2 4
 2 5
 3 4
 3 5
 4 5
 4 6
 5 6
<code>partialOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
nMAX = 200

def check_constraints(n, i, j):
    if not (1 <= n <= nMAX) or not (1 <= i <= n) or not (1 <= j <= n):
        with open("partialOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse")
        return False
    return True

def dfs(n, gf, viz, viznod):
    def dfs_util(nod):
        viznod[nod] = True
        for j in range(1, n + 1):
            if gf[nod][j] and not viznod[j]:
                viz[nod][j] = viz[j][nod] = True
                dfs_util(j)

    dfs_util(1)

def process_input():
    n, m = 0, 0
    gf = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]
    viz = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]
    viznod = [False] * (nMAX + 1)

    with open("partialIN.txt", "r") as fin:
        n = int(fin.readline().strip())
        if not check_constraints(n, 1, 1):
            return

        for line in fin:
            a, b = map(int, line.split())
            if not check_constraints(n, a, b):
                return

            gf[a][b] = gf[b][a] = True
            m += 1

    dfs(n, gf, viz, viznod)

    mfol = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if mfol != m // 2 and gf[i][j] and not viz[i][j]:
                gf[i][j] = gf[j][i] = False
                mfol += 1

    with open("partialOUT.txt", "w") as fout:
        if check_constraints(n, 1, 1):
            for i in range(1, n + 1):
                fout.write(' '.join(map(str, [int(x) for x in gf[i][1:n + 1]])) + '\n')

if __name__ == "__main__":
    process_input()

</syntaxhighlight>