Editing 3339 – Disjoint1

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>