Rus Marius: /* Date de ieșire */

2024-01-06T19:34:55Z

Date de ieșire

← Older revision		Revision as of 19:34, 6 January 2024
Line 6:		Line 6:

	= Date de ieșire =		= Date de ieșire =
	Fișierul de ieșire <code>partialOUT.txt</code> 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.		Fișierul de ieșire <code>partialOUT.txt</code> 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.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

	= Restricții și precizări =		= Restricții și precizări =

Rus Marius: Pagină nouă: = 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 <...

2024-01-06T19:34:43Z

Pagină nouă: = Cerința = Se dă un graf neorientat conex cu <code>n</code> 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 <code>partialIN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe a următoarele linii perechi de numere <code>i j</code>, cu semnificația că există muchie de la <code>i</code> la <...

New page

= Cerința =
Se dă un graf neorientat conex cu <code>n</code> 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 <code>partialIN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe a următoarele linii perechi de numere <code>i j</code>, cu semnificația că există muchie de la <code>i</code> la <code>j</code>.

= Date de ieșire =
Fișierul de ieșire <code>partialOUT.txt</code> 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 =

* <code>1 ≤ n ≤ 200</code>
* <code>1 ≤ i,j ≤ n</code>
* se garantează existența unui graf parțial cu proprietatea cerută

= Exemplul 1: =
<code>partialIN.txt</code>
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
<code>partialOUT.txt</code>
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: ==
<code>partialIN.txt</code>
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
<code>partialOUT.txt</code>
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>

0544 - Partial - Revision history

Rus Marius: /* Date de ieșire */