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

2024-01-06T19:18:10Z

Date de ieșire

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

	= Date de ieșire =		= Date de ieșire =
	Fișierul de ieșire <code>entriesOUT.txt</code> va conține răspunsurile la întrebări, câte un răspuns pe o linie, în ordinea din fișierul de intrare. Răspunsul va fi numărul <code>1</code> dacă nodurile despre care ați fost întrebat sunt în acel moment în aceeași componentă conexă, respectiv numărul <code>0</code> în caz contrar.		Fișierul de ieșire <code>entriesOUT.txt</code> va conține răspunsurile la întrebări, câte un răspuns pe o linie, în ordinea din fișierul de intrare. Răspunsul va fi numărul <code>1</code> dacă nodurile despre care ați fost întrebat sunt în acel moment în aceeași componentă conexă, respectiv numărul <code>0</code> în caz contrar.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

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

Rus Marius: Pagină nouă: == Enunț == Se consideră un graf care inițial este format din `P` noduri izolate, etichetate de la `1` la `P`. Se mai consideră `N` intrări, unde intrare poate însemna: * comandă – o comandă are forma `I + J`, cu semnificația că în graf se adaugă muchia care unește nodurile `I` și `J` (dacă `I` și `J` erau deja unite în acel moment, nu se întreprinde nici o...

2024-01-06T19:17:55Z

Pagină nouă: == Enunț == Se consideră un graf care inițial este format din <code>P</code> noduri izolate, etichetate de la <code>1</code> la <code>P</code>. Se mai consideră <code>N</code> intrări, unde intrare poate însemna: * comandă – o comandă are forma <code>I + J</code>, cu semnificația că în graf se adaugă muchia care unește nodurile <code>I</code> și <code>J</code> (dacă <code>I</code> și <code>J</code> erau deja unite în acel moment, nu se întreprinde nici o...

New page

== Enunț ==
Se consideră un graf care inițial este format din <code>P</code> noduri izolate, etichetate de la <code>1</code> la <code>P</code>. Se mai consideră <code>N</code> intrări, unde intrare poate însemna:

* comandă – o comandă are forma <code>I + J</code>, cu semnificația că în graf se adaugă muchia care unește nodurile <code>I</code> și <code>J</code> (dacă <code>I</code> și <code>J</code> erau deja unite în acel moment, nu se întreprinde nici o acțiune);
* întrebare – o întrebare este de forma <code>I ? J</code>, adică se întreabă dacă în acel moment <code>I</code> și <code>J</code> sunt în aceeași componentă conexă.

Se pleacă deci de la un graf inițial format din noduri izolate, care pe parcurs se “unifică”. Tot pe parcurs sunteți întrebat dacă anumite perechi de noduri sunt sau nu în aceeași componentă conexă.

= Cerința =
Scrieți un program care să răspundă la întrebările din fișierul de intrare.

= Date de intrare =
Din fișierul <code>entriesIN.txt</code> veți citi de pe prima linie numărul <code>N</code> de intrări. Pe următoarele <code>N</code> linii se găsesc intrările, câte una pe linie. O intrare este codificată prin trei numere separate prin câte un blanc. Primele două numere reprezintă nodurile <code>I</code> și <code>J</code> (numere întregi, cuprinse între <code>1</code> și <code>P</code>), iar al treilea este <code>1</code> dacă intrarea este o comandă, respectiv <code>2</code> dacă intrarea este o întrebare.

= Date de ieșire =
Fișierul de ieșire <code>entriesOUT.txt</code> va conține răspunsurile la întrebări, câte un răspuns pe o linie, în ordinea din fișierul de intrare. Răspunsul va fi numărul <code>1</code> dacă nodurile despre care ați fost întrebat sunt în acel moment în aceeași componentă conexă, respectiv numărul <code>0</code> în caz contrar.

= Restricții și precizări =

* <code>1 ≤ N ≤ 5 000</code>
* <code>1 ≤ P ≤ 10.000.000</code>

= Exemplul 1: =
<code>entriesIN.txt</code>
9
1 2 2
1 2 1
3 7 2
2 3 1
1 3 2
2 4 2
1 4 1
3 4 2
1 7 2
<code>entriesOUT.txt</code>
0
0
1
0
1
0

= Exemplul 2: =
<code>entriesIN.txt</code>
5001
1 2 2
1 2 1
3 7 2
2 3 1
1 3 2
2 4 2
1 4 1
3 4 2
1 7 2
<code>entriesOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictiile(n, p):
if not (1 <= n <= 5000):
raise ValueError("")
if not (1 <= p <= 10000000):
raise ValueError("")

def main():
fin = open("entriesIN.txt", "r")
fout = open("entriesOUT.txt", "w")

M = {}
t = [0] * 10005
n = 0

def find(x):
z, y = x, x
while t[x] != 0:
x = t[x]

while t[y] != 0:
z = t[y]
t[y] = x
y = z

return x

def union(x, y):
t[y] = x

T = int(fin.readline().strip())
try:
verifica_restrictiile(T, T) # Check restrictions for n (number of test cases)
except ValueError as e:
fout.write(f"Datele nu corespund restrictiilor impuse {str(e)}")
fin.close()
fout.close()
return

for _ in range(T):
x, y, op = map(int, fin.readline().strip().split())
k = 0
if x not in M:
k = 1
n += 1
M[x] = n
if y not in M:
k = 1
n += 1
M[y] = n

x = M[x]
y = M[y]
x = find(x)
y = find(y)

if op == 1:
if x != y:
union(x, y)
else:
if k == 1:
fout.write("0\n")
elif x == y:
fout.write("1\n")
else:
fout.write("0\n")

fin.close()
fout.close()

if __name__ == "__main__":
main()

</syntaxhighlight>

3235 - Entries - Revision history

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