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

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()