0418 - Subgraf - Revision history

Tita Marian at 20:12, 10 January 2024

2024-01-10T20:12:19Z

← Older revision		Revision as of 20:12, 10 January 2024
Line 14:		Line 14:

	== Exemplul 1 ==		== Exemplul 1 ==
	Subgrafin.txt		;Subgrafin.txt
	5		5
	1 4		1 4
Line 23:		Line 23:
	3 2		3 2
	4 3		4 3
	Subgrafout.txt		;Subgrafout.txt
	Datele de intrare respectă cerințele impuse		Datele de intrare respectă cerințele impuse
	1		1
Line 32:		Line 32:
	<br>		<br>
	== Exemplul 2 ==		== Exemplul 2 ==
	Subgrafin.txt		;Subgrafin.txt
	0		0
	Subgrafout.txt		;Subgrafout.txt
	Datele de intrare nu respectă cerințele impuse		Datele de intrare nu respectă cerințele impuse
	<br>		<br>

Tita Marian at 20:11, 10 January 2024

2024-01-10T20:11:44Z

← Older revision		Revision as of 20:11, 10 January 2024
Line 26:		Line 26:
	Datele de intrare respectă cerințele impuse		Datele de intrare respectă cerințele impuse
	1		1

			==Explicație==
			Se elimină vârfurile 2 3 5. Subgraful va conține vârfurile 1 4, cu o singură muchie.

	<br>		<br>
	== Exemplul 2 ==		== Exemplul 2 ==
Line 39:		Line 43:
	if num < 2:		if num < 2:
	return False		return False
	for i in range(2, int(num**0.5) + 1):		for i in range(2, int(num ** 0.5) + 1):
	if num % i == 0:		if num % i == 0:
	return False		return False
	return True		return True


	def count_edges_after_prime_removal(graph, n):		def count_edges_after_prime_removal(graph, n):
	primes = [i for i in range(2, n+1) if is_prime(i)]		primes = [i for i in range(2, n + 1) if is_prime(i)]
	vertices_to_remove = set(primes)		vertices_to_remove = set(primes)

	# Eliminăm vârfurile etichetate cu valori prime din graful original		# Eliminăm vârfurile etichetate cu valori prime din graful original
	new_graph = [(i, j) for (i, j) in graph if i not in vertices_to_remove and j not in vertices_to_remove]		new_graph = [(i, j) for (i, j) in graph if i not in vertices_to_remove and j not in vertices_to_remove]
Line 53:		Line 58:
	# Numărăm câte muchii rămân în subgraful obținut		# Numărăm câte muchii rămân în subgraful obținut
	return len(new_graph)		return len(new_graph)


			def is_adjacency_matrix(matrix, dimensiune):
			# Verificăm dacă matricea este pătratică
			if len(matrix) != dimensiune:
			return False

			# Verificăm dacă matricea este simetrică
			for i in range(dimensiune):
			for j in range(i + 1, dimensiune):
			if matrix[i][j] != matrix[j][i]:
			return False

			return True


	def main():		def main():
	try:		try:
	# Citim datele de intrare din fișierul "subgraf.in"		# Citim datele de intrare din fișierul "subgraf.in"
	with open("~~subgraf~~.in", "r") as fin:		with open("subgrafin.txt", "r") as fin:
	n = int(fin.readline().strip())		n = int(fin.readline().strip())
	graph = [tuple(map(int, line.split())) for line in fin.readlines()]		graph = [tuple(map(int, line.split())) for line in fin.readlines()]
Line 63:		Line 83:
	# Verificăm respectarea restricțiilor		# Verificăm respectarea restricțiilor
	if not (1 <= n <= 100) or any(not (1 <= i <= n and 1 <= j <= n) for i, j in graph):		if not (1 <= n <= 100) or any(not (1 <= i <= n and 1 <= j <= n) for i, j in graph):
	~~print~~("Datele de intrare nu respectă cerințele impuse")		with open("subgrafout.txt", "w", encoding="utf-8") as fout:
			fout.write("Datele de intrare nu respectă cerințele impuse\n")
	return		return
	else:		else:
	~~print~~("Datele de intrare respectă cerințele impuse")		with open("subgrafout.txt", "w", encoding="utf-8") as fout:
			fout.write("Datele de intrare respectă cerințele impuse\n")

	# Calculăm numărul de muchii în subgraful obținut		# Calculăm numărul de muchii în subgraful obținut
	result_edges = count_edges_after_prime_removal(graph, n)		result_edges = count_edges_after_prime_removal(graph, n)

	# Scriem rezultatul în fișierul "~~subgraf~~.~~out~~"		# Scriem rezultatul în fișierul "subgrafout.txt"
	with open("~~subgraf~~.~~out~~", "w") as fout:		with open("subgrafout.txt", "a", encoding="utf-8") as fout:
	fout.write(f"{result_edges}\n")		fout.write(f"{result_edges}\n")

	except Exception as e:		except Exception as e:
	~~print~~(f"Datele de intrare nu respectă cerințele impuse: {e}")		with open("subgrafout.txt", "w", encoding="utf-8") as fout:
			fout.write(f"Datele de intrare nu respectă cerințele impuse: {e}\n")
	~~if __name__ == "__main__":~~
	~~main()~~
	~~dimensiune = int(input()~~)

	~~# Citim matricea de adiacență de la tastatură~~
	~~matrix = []~~

	~~for _ in range(dimensiune):~~
	~~row = list(map(int, input().split()))~~
	~~matrix.append(row)~~

	~~# Verificăm dacă matricea este o matrice de adiacență~~
	~~result = count_edges_after_prime_removal(matrix, dimensiune)~~

	~~# Afișăm rezultatul~~
	~~print(result)~~

	if __name__ == "__main__":		if __name__ == "__main__":
	main()		main()

	</syntaxhighlight>		</syntaxhighlight>

	~~==Explicație==~~
	~~Se elimină vârfurile 2 3 5. Subgraful va conține vârfurile 1 4, cu o singură muchie.~~

Hotico Iulia Denisa: /* Rezolvare */

2024-01-09T18:12:03Z

Rezolvare

← Older revision		Revision as of 18:12, 9 January 2024
Line 79:		Line 79:

	if __name__ == "__main__":		if __name__ == "__main__":
	main() dimensiune = int(input())		main()
			dimensiune = int(input())

	# Citim matricea de adiacență de la tastatură		# Citim matricea de adiacență de la tastatură
Line 89:		Line 90:

	# Verificăm dacă matricea este o matrice de adiacență		# Verificăm dacă matricea este o matrice de adiacență
	result = ~~is_adjacency_matrix~~(matrix, dimensiune)		result = count_edges_after_prime_removal(matrix, dimensiune)

	# Afișăm rezultatul		# Afișăm rezultatul
Line 97:		Line 98:
	main()		main()
	</syntaxhighlight>		</syntaxhighlight>

	==Explicație==		==Explicație==
	Se elimină vârfurile 2 3 5. Subgraful va conține vârfurile 1 4, cu o singură muchie.		Se elimină vârfurile 2 3 5. Subgraful va conține vârfurile 1 4, cu o singură muchie.

Tita Marian: 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 vârfurile etichetate cu valori prime. Să se determine câte muchii va avea subgraful obținut. == Date de intrare == Fişierul de intrare '''subgrafin.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 semnific...

2023-12-06T17:27:38Z

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 vârfurile etichetate cu valori prime. Să se determine câte muchii va avea subgraful obținut. == Date de intrare == Fişierul de intrare '''subgrafin.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 semnific...

New page

== 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 vârfurile etichetate cu valori prime. Să se determine câte muchii va avea subgraful obținut.
== Date de intrare ==
Fişierul de intrare '''subgrafin.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 ==
Pe ecran se va afișa mesajul: '''"Datele de intrare respectă cerințele impuse"''' daca se respecta datele de intrare iar in caz contrar se afiseaza mesajul ''' “Datele de intrare nu respectă cerințele impuse” '''
Fişierul de ieşire '''subgrafout.txt'''va conţine pe prima linie numărul '''M''' de muchii ale subgrafului obținut.
== Restricţii şi precizări ==
* 1 &les; '''n''' &les; 100
* 1 &les; '''i, j''' &les; n
* muchiile se pot repeta în fișierul de intrare

== Exemplul 1 ==
Subgrafin.txt
5
1 4
2 5
2 3
2 1
4 5
3 2
4 3
Subgrafout.txt
Datele de intrare respectă cerințele impuse
1
<br>
== Exemplul 2 ==
Subgrafin.txt
0
Subgrafout.txt
Datele de intrare nu respectă cerințele impuse
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_prime(num):
if num < 2:
return False
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
return False
return True

def count_edges_after_prime_removal(graph, n):
primes = [i for i in range(2, n+1) if is_prime(i)]
vertices_to_remove = set(primes)

# Eliminăm vârfurile etichetate cu valori prime din graful original
new_graph = [(i, j) for (i, j) in graph if i not in vertices_to_remove and j not in vertices_to_remove]

# Numărăm câte muchii rămân în subgraful obținut
return len(new_graph)

def main():
try:
# Citim datele de intrare din fișierul "subgraf.in"
with open("subgraf.in", "r") as fin:
n = int(fin.readline().strip())
graph = [tuple(map(int, line.split())) for line in fin.readlines()]

# Verificăm respectarea restricțiilor
if not (1 <= n <= 100) or any(not (1 <= i <= n and 1 <= j <= n) for i, j in graph):
print("Datele de intrare nu respectă cerințele impuse")
return
else:
print("Datele de intrare respectă cerințele impuse")

# Calculăm numărul de muchii în subgraful obținut
result_edges = count_edges_after_prime_removal(graph, n)

# Scriem rezultatul în fișierul "subgraf.out"
with open("subgraf.out", "w") as fout:
fout.write(f"{result_edges}\n")

except Exception as e:
print(f"Datele de intrare nu respectă cerințele impuse: {e}")

if __name__ == "__main__":
main() dimensiune = int(input())

# Citim matricea de adiacență de la tastatură
matrix = []

for _ in range(dimensiune):
row = list(map(int, input().split()))
matrix.append(row)

# Verificăm dacă matricea este o matrice de adiacență
result = is_adjacency_matrix(matrix, dimensiune)

# Afișăm rezultatul
print(result)

if __name__ == "__main__":
main()
</syntaxhighlight>
==Explicație==
Se elimină vârfurile 2 3 5. Subgraful va conține vârfurile 1 4, cu o singură muchie.