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.

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

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