Corjuc Eunice at 15:00, 16 December 2023

2023-12-16T15:00:15Z

← Older revision		Revision as of 15:00, 16 December 2023
Line 3:		Line 3:

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

	= Date de ieşire =		= Date de ieşire =
	Fişierul de ieşire <code>~~graf_partial_1~~.~~out~~</code> 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.		Fişierul de ieşire <code>graf_partial_1OUT.txt</code> 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 =		= Restricţii şi precizări =

Corjuc Eunice: Pagină nouă: = 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_1.in` conţine pe prima linie numărul
2023-12-16T14:38:27Z

Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri, etichetate de la <code>1</code> la <code>n</code>. 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 <code>graf_partial_1.in</code> conţine pe prima linie numărul <cod...

New page
= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri, etichetate de la <code>1</code> la <code>n</code>. 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 <code>graf_partial_1.in</code> conţine pe prima linie numărul <code>n</code>, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

= Date de ieşire =
Fişierul de ieşire <code>graf_partial_1.out</code> 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 =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* 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>