Corjuc Eunice: Pagină nouă: Se consideră un graf cu `N` noduri numerotate de la `1` la `N` și `M` operații de trei tipuri: * `1 x y` – se adaugă în graf muchia `(x, y)`. Dacă muchia există deja, operația nu se efectuează * `2 x y` – întrebare: nodurile `x` și `y` se află sau nu în aceeași componentă conexă? * `3` – întrebare: care este numărul maxim de noduri dintr-o com...

2024-01-03T21:01:52Z

Pagină nouă: Se consideră un graf cu <code>N</code> noduri numerotate de la <code>1</code> la <code>N</code> și <code>M</code> operații de trei tipuri: * <code>1 x y</code> – se adaugă în graf muchia <code>(x, y)</code>. Dacă muchia există deja, operația nu se efectuează * <code>2 x y</code> – întrebare: nodurile <code>x</code> și <code>y</code> se află sau nu în aceeași componentă conexă? * <code>3</code> – întrebare: care este numărul maxim de noduri dintr-o com...

New page

Se consideră un graf cu <code>N</code> noduri numerotate de la <code>1</code> la <code>N</code> și <code>M</code> operații de trei tipuri:

* <code>1 x y</code> – se adaugă în graf muchia <code>(x, y)</code>. Dacă muchia există deja, operația nu se efectuează
* <code>2 x y</code> – întrebare: nodurile <code>x</code> și <code>y</code> se află sau nu în aceeași componentă conexă?
* <code>3</code> – întrebare: care este numărul maxim de noduri dintr-o componentă conexă?

= Cerința =
Trebuie să răspundeți la toate întrebările de tip <code>2</code> și <code>3</code>.

= Date de intrare =
Programul citește de la tastatură numerele <code>N</code> și <code>M</code>, iar pe următoarele <code>M</code> linii se află operațiile date fie prin trei valori de forma <code>op x y</code> (pentru operațiile de tip <code>1</code> și <code>2</code>), fie printr-o singură valoare <code>3</code> (pentru operațiile de tip <code>3</code>).

= Date de ieșire =
Programul va afișa pe ecran, pe câte o linie, răspunsul la fiecare întrebare de tip <code>2</code> și <code>3</code>. Dacă la o întrebare <code>2 x y</code> răspunsul este afirmativ, adică <code>x</code> și <code>y</code> se află în aceeași componentă conexă, atunci veți afișa <code>DA</code>, iar în caz contrar veți afișa <code>NU</code>.

= Restricții și precizări =

* <code>3 ≤ N ≤ 32.000</code>
* <code>3 ≤ M ≤ 300.000</code>
* va exista cel puțin o operație de fiecare tip.

== Exemplul 1 ==
Input:

6 6

1 1 4

1 3 6

2 4 6

1 1 3

2 4 6

3

Output:

NU

DA

4

== Exemplul 2 ==
Input:

99999999 6

1 1 4

1 3 6

2 4 6

1 1 3

2 4 6

3

Output:

Invalid input. Please ensure that 3 ≤ N ≤ 32,000 and 3 ≤ M ≤ 300,000.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verify_conditions(N, M):
return 3 <= N <= 32000 and 3 <= M <= 300000

class UnionFind:
def __init__(self, n):
self.parent = list(range(n + 1))
self.rank = [0] * (n + 1)
self.size = [1] * (n + 1)
self.max_size = 1

def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]

def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)

if root_x != root_y:
if self.rank[root_x] < self.rank[root_y]:
root_x, root_y = root_y, root_x
self.parent[root_y] = root_x
self.size[root_x] += self.size[root_y]
self.max_size = max(self.max_size, self.size[root_x])
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1

def main():
N = int(input())
M = int(input())

if not verify_conditions(N, M):
print("Invalid input. Please ensure that 3 ≤ N ≤ 32,000 and 3 ≤ M ≤ 300,000.")
return

union_find = UnionFind(N)

for _ in range(M):
input_values = input().split()
operation = int(input_values[0])

if operation == 1:
x, y = int(input_values[1]), int(input_values[2])
union_find.union(x, y)
elif operation == 2:
x, y = int(input_values[1]), int(input_values[2])
result = "DA" if union_find.find(x) == union_find.find(y) else "NU"
print(result)
elif operation == 3:
print(union_find.max_size)

if __name__ == "__main__":
main()
</syntaxhighlight>

3339 – Disjoint1 - Revision history