3339 – Disjoint1

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 componentă conexă?

Cerința

Trebuie să răspundeți la toate întrebările de tip 2 și 3.

Date de intrare

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

Date de ieșire

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

Restricții și precizări

• 3 ≤ N ≤ 32.000
• 3 ≤ M ≤ 300.000
• 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>