0544 - Partial

Cerința

Se dă un graf neorientat conex cu n 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 partialIN.txt conține pe prima linie numărul n, iar pe a următoarele linii perechi de numere i j, cu semnificația că există muchie de la i la j.

Date de ieșire

Fișierul de ieșire partialOUT.txt 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

• 1 ≤ n ≤ 200
• 1 ≤ i,j ≤ n
• se garantează existența unui graf parțial cu proprietatea cerută

Exemplul 1:

partialIN.txt

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

partialOUT.txt

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:

partialIN.txt

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

partialOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

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()