Daily 19/08/2023: [1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree](https://leetcode.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/)

# 1. Tóm tắt đề bài
Cho một đồ thị liên thông vô hướng có trọng số với n đỉnh được đánh số từ 0 đến n - 1 và một mảng các cạnh trong đó các $edge[i] = [a_{i}, b_{i}, weight_{i}]$ đại diện cho cạnh hai chiều và có trọng số giữa các nút ai và bi. Cây khung nhỏ nhất (MST) là một tập hợp con gồm các cạnh của đồ thị kết nối tất cả các đỉnh không có chu trình và với tổng trọng số cạnh nhỏ nhất có thể.

Tìm tất cả các cạnh **critical** và **pseudo-critical** trong cây khung nhỏ nhất (MST) của đồ thị đã cho. Cạnh MST bị xóa khỏi đồ thị sẽ làm tăng trọng số MST được gọi là cạnh **critical**. Mặt khác, cạnh **pseudo-critical** là cạnh xuất hiện trong một số MST nhưng không nhất thiết phải xuất hiện trong tất cả MST.

**Lưu ý:** Có thể trả về chỉ số của các cạnh theo thứ tự bất kỳ.

#### Giới hạn
- $2 \le n \le 100$
- $1 \le edge.length \le min(200, \frac{n * (n - 1)}{2}) $
- $0 \le a_{i} < b_{i} <n$
- $1 \le weight_{i} \le 1000$
- Các cặp $(a_{i}, b_{i})$ luôn khác nhau

# 2 .Tóm tắt lời giải
#### Cách tiếp cận
Trước khi làm bài này, bạn đọc có thể tìm hiểu trước các bài toán cơ bản về [cây khung nhỏ nhất (MST)](https://vnoi.info/wiki/algo/graph-theory/minimum-spanning-tree.md) và cách cài đặt [Disjoint Set Union (DSU)](https://vnoi.info/wiki/algo/graph-theory/minimum-spanning-tree.md).

Với các dạng bài về cây khung nhỏ nhất thì đa số chúng ta đều dùng thuật toán **Krusal** với cấu trúc dữ liệu **Disjoint Set**. Bài này cũng không phải ngoại lệ, tuy nhiên thì bài toán yêu cầu là cần tìm các cạnh **critical** và **pseudo-critical** và với giới hạn $n \le 100$ thì chúng ta hoàn toàn có thể chạy các thuật $O(n^{2})$.

#### Hướng giải
Vì giới hạn khá bé nên chúng ta có thể nghĩ tới hướng là xét từng cạnh một xong xét cạnh đấy là kiểu cạnh nào luôn.

# 3. Lời giải chi tiết
Chúng ta phải xây dựng cấu trúc DSU thành một class luôn vì phải sử dụng nhiều lần. Thực hiện lần lượt các bước sau
- Các cạnh trong $edges$ thì thêm thuộc tính vị trí ban đầu của nó.
- Sau đó sắp xếp $edges$ theo trọng số ($weight$)
- Rồi dùng thuật toán **Krusal** tìm giá trị trọng số của cây khung nhỏ nhất
- Dùng vòng for xét từng cạnh một, rồi thực hiện tìm cây khung nhỏ nhất mà không chứa cạnh đấy, tính trọng số của cây khung đó.
- Nếu cây khung không tồn tại hoặc trọng số của cây khung đó lớn hơn trọng số cây khung nhỏ nhất ban đầu của đồ thị thì chúng ta thêm cạnh đó vào tập cạnh **critical**
- Còn không thì lại tìm cây khung nhỏ nhất bắt buộc chứa cạnh đấy rồi xem trọng số cây khung đó có bằng trọng số cây khung nhỏ nhất ban đầu không. Nếu có thì thêm vào tập **psudo-critical**

#### Code

class DSU:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [1] * n

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

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

        if self.rank[x] >= self.rank[y]:
            self.rank[x] += self.rank[y]
            self.par[y] = x
        else:
            self.rank[y] += self.rank[x]
            self.par[x] = y

class Solution:
    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        m: int = len(edges)
        for i, edge in enumerate(edges):
            edge.append(i)

        edges = sorted(edges, key=lambda x: x[2])

        dsu = DSU(n)
        critical, pseudo_critical = [], []

        mst_weight = 0
        for edge in edges:
            if dsu.find(edge[0]) != dsu.find(edge[1]):
                dsu.union(edge[0], edge[1])
                mst_weight += edge[2]

        for i in range(m):
            tmp_weight = 0
            tmp_dsu = DSU(n)
            for j in range(m):
                edge = edges[j]
                if i != j and tmp_dsu.find(edge[0]) != tmp_dsu.find(edge[1]):
                    tmp_dsu.union(edge[0], edge[1])
                    tmp_weight += edge[2]
            
            if tmp_dsu.rank[tmp_dsu.find(0)] != n or tmp_weight > mst_weight:
                critical.append(edges[i][3])
            else:
                new_dsu = DSU(n)
                new_dsu.union(edges[i][0], edges[i][1])

                weight = edges[i][2]

                for j in range(m):
                    edge = edges[j]
                    if i != j and new_dsu.find(edge[0]) != new_dsu.find(edge[1]):
                        new_dsu.union(edge[0], edge[1])
                        weight += edge[2]

                
                if weight == mst_weight:
                    pseudo_critical.append(edges[i][3])
        
        return [critical, pseudo_critical]

#### Độ phức tạp thuật toán
Thời gian: $O(m^{2} + mlog(n)) = O(m^{2})$ với m là số cạnh và n là số đỉnh.
Bộ nhớ: $O(nm)$ ???
# 4. Kết luận & gợi ý mở rộng
Bài toán tay to vì không phải vì thuật toán khó mà nó là phải code nhiều và cũng phải thông thạo cấu trúc dữ liệu.