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

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)