0421 - Graf Partial 1

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Din acest graf se elimină toate muchiile cu o extremitate de grad maxim și cealaltă extremitate de grad minim. Să se determine numărul de muchii eliminate și să se afișeze matricea de adiacență a grafului parțial obținut.

Date de intrare

Fişierul de intrare graf_partial_1IN.txt conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire graf_partial_1OUT.txt va conţine pe prime linie numărul de muchii eliminate, iar pe următoarele linii matricea de adiacență a grafului parțial obținut, câte o linie a matricei pe o linie a fișierului, elementele de pe fiecare linie fiind separate prin exact un spațiu.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• muchiile se pot repeta în fișierul de intrare

Exemplul 1

graf_partial_1IN.txt:

6

1 3

2 3

2 4

4 3

5 3

4 5

3 1

6 4

graf_partial_1OUT.txt:

2

0 0 0 0 0 0

0 0 1 1 0 0

0 1 0 1 1 0

0 1 1 0 1 0

0 0 1 1 0 0

0 0 0 0 0 0

Exemplul 2

graf_partial_1IN.txt:

999

1 3

2 3

2 4

4 3

5 3

4 5

3 1

6 4

Output:

Restrictiile nu sunt indeplinite.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def check_input_restrictions(n, edges):

   if not (1 <= n <= 100):
       return False

   for edge in edges:
       i, j = edge
       if not (1 <= i <= n) or not (1 <= j <= n):
           return False

   return True

def read_graph(filename):

   with open(filename, 'r') as file:
       n = int(file.readline())
       edges = [tuple(map(int, line.split())) for line in file.readlines()]

   if not check_input_restrictions(n, edges):
       print("Restrictiile nu sunt indeplinite.")
       return None

   return n, edges

def read_graph(filename):

   with open(filename, 'r') as file:
       n = int(file.readline())
       edges = [tuple(map(int, line.split())) for line in file.readlines()]
   return n, edges

def write_output(filename, result):

   with open(filename, 'w') as file:
       file.write(str(result['num_edges_removed']) + '\n')
       for row in result['adjacency_matrix']:
           file.write(' '.join(map(str, row)) + '\n')

def build_adjacency_matrix(n, edges):

   adjacency_matrix = [[0] * n for _ in range(n)]
   for edge in edges:
       i, j = edge
       adjacency_matrix[i-1][j-1] = adjacency_matrix[j-1][i-1] = 1
   return adjacency_matrix

def calculate_degrees(adjacency_matrix):

   degrees = [sum(row) for row in adjacency_matrix]
   return degrees

def eliminate_edges(adjacency_matrix, degrees):

   max_degree = max(degrees)
   min_degree = min(degrees)

   max_degree_nodes = [i for i in range(len(degrees)) if degrees[i] == max_degree]
   min_degree_nodes = [i for i in range(len(degrees)) if degrees[i] == min_degree]
   
   edges_removed = 0
   for i in max_degree_nodes:
       for j in min_degree_nodes:
           if adjacency_matrix[i][j] == 1:
               adjacency_matrix[i][j] = adjacency_matrix[j][i] = 0
               edges_removed += 1

   return edges_removed

if __name__ == "__main__":

   input_filename = "graf_partial_1IN.txt"
   output_filename = "graf_partial_1OUT.txt"

   graph_data = read_graph(input_filename)

   if graph_data is not None:
       n, edges = graph_data

       adjacency_matrix = build_adjacency_matrix(n, edges)
       degrees = calculate_degrees(adjacency_matrix)

       num_edges_removed = eliminate_edges(adjacency_matrix, degrees)

       result = {
           'num_edges_removed': num_edges_removed,
           'adjacency_matrix': adjacency_matrix
       }

       write_output(output_filename, result)

</syntaxhighlight>