# Coding Challenge #1

## Đề Bài

:::spoiler Đề bài gốc có thể được đọc trên hệ thống [VNOJ](https://oj.vnoi.info/problem/coding_challenge_duongdi)
**Coding Challenge #1 - Đường đi**

Cho một đồ thị vô hướng gồm $N$ đỉnh, ban đầu đồ thị này không có cạnh nào. Mỗi đỉnh thứ $i$ được gán một màu $c_i$.
Bạn cần thực hiện lần lượt $Q$ thao tác, mỗi thao tác thuộc một trong hai loại sau:

- Loại 1: `1 x y` - nối toàn bộ các đỉnh có màu $x$ với toàn bộ các đỉnh có màu $y$.

- Loại 2: `2 u v` - đổi màu của toàn bộ các đỉnh $i$ có $c_i = u$ thành $c_i = v$.

Sau khi thực hiện xong tất cả các thao tác, hãy in ra độ dài đường đi ngắn nhất từ đỉnh $1$ tới toàn bộ các đỉnh trong đồ thị.

**Input**

- Dòng đầu tiên chứa hai số nguyên $N, Q$ $(1 \le N, Q \le 3 \times 10^5)$.

- Dòng thứ hai chứa $N$ số nguyên $c_1, c_2, ..., c_N$ - màu ban đầu của từng đỉnh $(1 \le c_i \le N)$.

- $Q$ dòng tiếp theo, mỗi dòng chứa 3 số nguyên $t, x, y$ mô tả các thao tác $(1 \le t \le 2, 1 \le x, y \le N)$.

**Output**

- In ra $N$ số nguyên, số thứ $i$ là độ dài đường đi ngắn nhất từ đỉnh $1$ tới đỉnh $i$. Nếu không tồn tại đường đi, in ra $-1$.

**Scoring**

| Subtask | Điểm | Giới hạn |
| :--- | :--- | :--- |
| $1$ | 20% | $N, Q \le 100$ |
| $2$ | 30% | Chỉ có thao tác loại $1$ |
| $3$ | 20% | Tất cả thao tác loại $2$ xuất hiện trước thao tác loại $1$ |
| $4$ | 30% | Không có giới hạn bổ sung |

**Sample Input 1**

5 4
1 2 3 2 1
1 1 2
2 3 2
1 2 3
1 1 3

**Sample Output 1**

0 1 -1 1 2

**Notes**

• Ban đầu: chưa có cạnh nào;

• Thao tác `1 1 2`: Nối toàn bộ đỉnh màu $1$ với toàn bộ đỉnh màu $2$ $\Rightarrow$ Tạo cạnh giữa các đỉnh ${1, 5}$ với ${2, 4}$;

• Thao tác `2 3 2`: Đổi toàn bộ đỉnh màu $3$ thành màu $2$ $\Rightarrow$ Đỉnh $3$ có màu $2$;

• Thao tác `1 2 3`: Không có thay đổi gì vì không còn đỉnh nào có màu $3$;

• Thao tác `1 1 3`: Không có thay đổi gì vì không còn đỉnh nào có màu $3$.

Sau cùng, đường đi ngắn nhất từ đỉnh $1$ đến các đỉnh khác là:

• Đỉnh $1$ $\rightarrow$ chính nó: $0$

• Đỉnh $2$: $1$ $\rightarrow$ $2$ (độ dài $1$)

• Đỉnh $3$: Không tồn tại đường đi ($-1$)

• Đỉnh $4$: $1$ $\rightarrow$ $4$ (độ dài $1$)

• Đỉnh $5$: $1 \rightarrow 2 \rightarrow 5$ (độ dài $2$)
:::

:::spoiler Minh họa test ví dụ


:::

## Lời Giải

### Subtask 1

- **Giới hạn bổ sung:** $N, Q \le 100$

:::spoiler Ý tưởng

- Vì giới hạn của subtask này là nhỏ, chúng ta có thể giải quyết subtask này bằng cách thực hiện chính xác như những gì đề yêu cầu.

- Với thao tác loại $1$ với hai màu $x$ và $y$, chúng ta duyệt tuần tự để tìm tập các đỉnh có màu $x$ và tập các đỉnh có màu $y$ rồi với mỗi cặp đỉnh từ hai tập, ta thêm cạnh nối hai chiều giữa hai đỉnh.

- Với thao tác loại $2$ với hai màu $u$ và $v$, chúng ta duyệt tuần tự và gán màu $v$ cho các đỉnh có màu $u$

$$ c[i] \leftarrow v \quad \forall \, (c[i] = u) $$

- Sau khi thực hiện xong tất cả các thao tác, để tìm ra độ dài đường đi ngắn nhất từ đỉnh $1$ tới toàn bộ các đỉnh trong đồ thị, ta có thể sử dụng thuật toán [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) từ đỉnh $1$ trên đồ thị không trọng số dựng được.

:::

:::spoiler Độ phức tạp

- Cách giải như trên có độ phức tạp về thời gian là $O(Q \cdot N^2)$ trong trường hợp xấu nhất

- Quá trình đọc dữ liệu có độ phức tạp về thời gian là $O(N + Q)$

- Với mỗi thao tác loại $1$, vì mỗi màu có $O(N)$ đỉnh có màu đó, ta sẽ phải xem xét qua $O(N^2)$ cặp đỉnh cho hai màu $x$ và $y$.

- Với mỗi thao tác loại $2$, ta phải quyệt qua $O(N)$ đỉnh.

- Bước chạy thuật toán [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) sẽ có độ phức tạp về thời gian là $O(N + |E|)$ với $|E|$ là số cạnh của đồ thị sau khi ta đã dựng xong. Vì dữ liệu có thể chứa $O(Q)$ thao tác loại $1$, ta có $|E| = O(Q \cdot N^2)$. Nói cách khác, bước xử lý tìm đường đi ngắn nhất có độ phức tạp $O(Q \cdot N^2)$

- Tương tự, độ phức tạp bộ nhớ của cách giải trên là $O(Q \cdot N^2)$ trong trường hợp tệ nhất bởi ta phải lưu $O(Q \cdot N^2)$ cạnh đồng thời cùng một lúc

:::

:::spoiler Code minh họa

#include <bits/stdc++.h>

using namespace std;

template<class A, class B>
bool maximize(A &a, const B& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class A, class B>
bool minimize(A &a, const B& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 300'005, INF = 0X3F3F3F3F;

int N, Q, c[MAX_N];
vector<int> graph[MAX_N];
signed minimumDistance[MAX_N];

void addEdges(const int x, const int y) {
    for (int i = 1; i <= N; ++i) {
        if (c[i] != x)
            continue;
        for (int j = 1; j <= N; ++j) {
            if (c[j] != y)
                continue;
            graph[i].push_back(j);
            graph[j].push_back(i);
        }
    }
}

void changeColors(const int u, const int v) {
    for (int i = 1; i <= N; ++i)
        if (c[i] == u)
            c[i] = v;
}

void runBFS() {
    queue<int> q;

    minimumDistance[1] = 0;
    q.push(1);

    for (; !q.empty(); q.pop()) {
        const int &x = q.front();
        for (const int &y : graph[x])
            if (minimize(minimumDistance[y], minimumDistance[x] + 1))
                q.push(y);
    }
}

int main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> Q;

    for (int i = 1; i <= N; ++i) {
        minimumDistance[i] = INF;
        cin >> c[i];
    }

    for (int q = 1, t = 0, x = 0, y = 0; q <= Q; ++q) {
        cin >> t >> x >> y;
        if (t == 1)
            addEdges(x, y);
        else
            changeColors(x, y);
    }

    runBFS();

    for (int i = 1; i <= N; ++i)
        cout << ((minimumDistance[i] < INF) ? minimumDistance[i] : (-1)) << ' ';

    cout << '\n';

    return 0;
}

:::

### Subtask 2

- **Giới hạn bổ sung:** Chỉ có thao tác loại $1$

:::spoiler Ý tưởng

- Với giới hạn của subtask này, ta có nhận xét rằng với hai đỉnh $x$ và $y$ đều khác $1$ và có cùng màu thì đường đi ngắn nhất từ đỉnh $1$ đến đỉnh $x$ và $y$ nên bằng nhau.
Nếu ta đặt $d[i]$ là độ dài đường đi ngắn nhất từ đỉnh $1$ đến đỉnh $i$, ta có: $$\forall x, y \, (c[x] = c[y]) \land (x \neq 1) \land (y \neq 1) \rightarrow d[x] = d[y]$$
>[!Note] **Chứng minh chi tiết:**
> - Giả sử tồn tại hai đỉnh $x$ và $y$ đều khác $1$ và có cùng màu nhưng đường đi ngắn nhất từ đỉnh $1$ đến hai đỉnh $x$ và $y$ lại khác nhau. Không làm mất tính tổng quát, ta xét trường hợp $d[x] < d[y]$
> - Xét một đường đi ngắn nhất bất kì từ $1$ đến $x$, gọi $z$ là đỉnh ngay trước $x$ trên đường đi đó ($1 \rightarrow ... \rightarrow z \rightarrow x$). Vì đồ thị chứa cạnh từ $z$ tới $x$, danh sách thao tác phải bao gồm ít nhất một thác như sau: `1 c[z] c[x]`. Vì đỉnh $x$ và $y$ có cùng màu ($c[x] = c[y]$), đồ thị cũng chứa cạnh từ $z$ tới $y$. Điều này đồng nghĩa với việc tồn tại đường đi từ $1$ tới $y$ với độ dài $d[z] + 1 = d[x]$ mà $d[x] < d[y]$ (theo giả định trước đó)
> $\Rightarrow$ Tồn tại đường đi từ $1$ tới $y$ với độ dài ngắn hơn $d[y]$; mâu thuẫn với định nghĩa của $d[y]$

- Từ nhận xét này, ta nhận thấy rằng trừ đỉnh $1$, các đỉnh chỉ có thể được phân biệt với nhau bằng màu (nói cách khác, không có sự phân biệt giữa các đỉnh cùng màu).
Dựa vào đây, ta có thể dùng màu để đại diện cho các đỉnh đó. Cụ thể hơn, thay vì xây dựng đồ thị như đề bài (với số cạnh trong trường hợp tệ nhất đạt xấp xỉ $Q \cdot N^2$), ta có thể xây dựng một đồ thị khác $G' = (V', E')$ có các đỉnh là các màu và có cạnh giữa $x'$ và $y'$ nếu tồn tại thao tác `1 x' y'`.
$\Rightarrow$ Số cạnh của đồ thị $G'$ sẽ không vượt quá $Q$ ($|E'| = O(Q)$), cho phép chúng ta tìm đường đi ngắn nhất giữa đỉnh đại diện cho màu của đỉnh $1$ và các đỉnh còn lại trong $V'$ với độ phức tạp cho phép.
Nếu đặt $T = \{(t_i, x_i, y_i) \, | \, 1 \leq i \leq Q\}$ là tập hợp các thao tác sử dụng, ta có:
- $V' = \{c[u] \, | \, 1 \leq u \leq N \}$
- $E' = \{(x, y) \, | \, ((1, x, y) \in T) \land (x, y \in V') \}$

- Với các đỉnh $x$ có màu khác với màu của đỉnh $1$ ($c[x] \neq c[1]$), độ dài đường đi ngắn nhất từ $1$ tới $x$ sẽ bằng với độ dài đường đi ngắn nhất từ $c[1]$ tới $c[x]$ trong $G'$.

- Với các đỉnh $x$ không phải là đỉnh $1$ nhưng có cùng màu với đỉnh $1$ ($c[x] = c[1]$), ta sẽ có ba trường hợp sau:
- Tồn tại thao tác `1 c[1] c[1]` (nối giữa các đỉnh có màu $c[1]$ với nhau)
$\Rightarrow$ Độ dài đường đi ngắn nhất từ $1$ tới $x$ bằng $1$.
- Không tồn tại thao tác như trên nhưng $c[1]$ có cạnh nối tới màu khác (trong $G'$)
$\Rightarrow$ Độ dài đường đi ngắn nhất từ $1$ tới $x$ bằng $2$ (ta tốn một bước để từ đỉnh $1$ đi đến một đỉnh bất kì có màu kề với $c[1]$ rồi đi đến $x$).
- Các điều kiện trên đều không thỏa
$\Rightarrow$ Không tồn tại đường đi giữa $1$ và $x$

:::

:::spoiler Độ phức tạp

- Cách giải như trên có độ phức tạp về thời gian là $O(N + Q)$ trong trường hợp xấu nhất bởi việc dựng đồ thị và tìm đường đi ngắn nhất (với thuật toán [BFS](https://en.wikipedia.org/wiki/Breadth-first_search)) có độ phức tạp $O(N + Q)$.

- Tương tự, độ phức tạp bộ nhớ của cách giải trên là $O(N + Q)$ trong trường hợp tệ nhất.

:::

:::spoiler Code minh họa

#include <bits/stdc++.h>

using namespace std;

template<class A, class B>
bool maximize(A &a, const B& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class A, class B>
bool minimize(A &a, const B& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 300'005, INF = 0X3F3F3F3F;

int N, Q, c[MAX_N];
bool existed[MAX_N];
vector<int> graph[MAX_N];
signed minimumDistance[MAX_N];

void runBFS() {
    queue<int> q;

    minimumDistance[c[1]] = 0;
    q.push(c[1]);

    for (; !q.empty(); q.pop()) {
        const int &x = q.front();
        for (const int &y : graph[x])
            if (minimize(minimumDistance[y], minimumDistance[x] + 1))
                q.push(y);
    }
}

int main() {
    bool sourceFlag = false;

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> Q;

    for (int i = 1; i <= N; ++i) {
        minimumDistance[i] = INF;
        cin >> c[i];
        existed[c[i]] = true;
    }

    for (int q = 1, t = 0, x = 0, y = 0; q <= Q; ++q) {
        cin >> t >> x >> y;
        if (!existed[x] || !existed[y])
            continue;
        graph[x].push_back(y);
        graph[y].push_back(x);
        if (x == c[1] && y == c[1])
            sourceFlag = true;
    }

    runBFS();

    cout << 0 << ' ';

    for (int i = 2; i <= N; ++i) {
        if (c[i] != c[1]) {
            cout << ((minimumDistance[c[i]] < INF) ? minimumDistance[c[i]] : (-1)) << ' ';
            continue;
        }
        cout << (sourceFlag ? 1 : ((!graph[c[1]].empty()) ? 2 : (-1))) << ' ';
    }

    cout << '\n';

    return 0;
}

:::

### Subtask 3

- **Giới hạn bổ sung:** Tất cả thao tác loại $2$ xuất hiện trước thao tác loại $1$

:::spoiler Ý tưởng

- Ta nhận thấy rằng, nếu ta có thể cập nhật được màu các đỉnh sau khi xử lý xong các thao tác loại $2$ (với độ phức tạp hợp lý), bài toán sẽ được đưa về [subtask $2$](https://hackmd.io/2Fp-DrFwSa2vuYYHOOW0UQ?both=#Subtask-2).

- Ta có nhận xét rằng mỗi thao tác loại $2$ có thể được xem như gồm hai bước:
- Gộp hai tập đỉnh lại thành một tập đỉnh.
- Đánh số (tên màu) lại tập đỉnh mới.
Ví dụ như trong sample test được đưa ra, thao tác `2 3 2` (thao tác thứ $2$ trong danh sách các thao tác) có thể được xem như việc gộp tập đỉnh $\{2, 4\}$ (có màu $2$) và $\{3\}$ (có màu $3$) thành tập đỉnh mới $\{2, 3, 4\}$ và đánh màu $2$ cho tập đỉnh này.

- Dựa trên nhật xét này và giới hạn của subtask, chúng ta có thể sử dụng cấu trúc dữ liệu [Disjoint Set Union](https://cp-algorithms.com/data_structures/disjoint_set_union.html) để thực hiện các thao tác loại $2$ và cập nhật màu của đỉnh.

>[!Warning] Lưu Ý:
> Ý tưởng chỉ có thể giải quyết [subtask $3$](https://hackmd.io/2Fp-DrFwSa2vuYYHOOW0UQ?both=#Subtask-3) (và [subtask $2$](https://hackmd.io/2Fp-DrFwSa2vuYYHOOW0UQ?both=#Subtask-2)), không thể áp dụng trong mọi trường hợp. Khi các thao tác loại $1$ và loại $2$ được thực hiện đan xen, một màu có thể có tập đỉnh thay đổi theo thời gian.

:::

:::spoiler Độ phức tạp

- Độ phức tạp về thời gian của ý tưởng nêu trên có thể là $O(Q \cdot \alpha(N) + N)$ hoặc $O(Q \cdot \log(N) + N)$ (tùy thuộc vào cách ta cài đặt cấu trúc dữ liệu [Disjoint Set Union](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)):
- Nếu cấu trúc dữ liệu [Disjoint Set Union](https://wiki.vnoi.info/algo/data-structures/disjoint-set-union) được cài đặt với cả hai phương pháp gộp theo kích cỡ và nén đường đi thì độ phức tạp trung bình cho mỗi lần gộp tập đỉnh là $O(\alpha(N))$ (với $\alpha(N)$ là [hàm Ackermann nghịch đảo](https://en.wikipedia.org/wiki/Ackermann_function#Inverse)).
Nếu chỉ một trong hai phương pháp được sử dụng thì độ phức tạp cho mỗi lần gộp tập đỉnh là $O(\log(N))$.
- Độ phức tạp của các bước xử lý còn lại của cách giải đã nêu sẽ tương tự với cách giải cho [subtask $2$](https://hackmd.io/2Fp-DrFwSa2vuYYHOOW0UQ?both=#Subtask-2) trước đó, tức $O(N + Q)$.

- Độ phức tạp về bộ nhớ của cách giải trên sẽ tương tự với [subtask $2$](https://hackmd.io/2Fp-DrFwSa2vuYYHOOW0UQ?both=#Subtask-2), tức $O(N + Q)$.

:::

:::spoiler Code minh họa

#include <bits/stdc++.h>

using namespace std;

template<class A, class B>
bool maximize(A &a, const B& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class A, class B>
bool minimize(A &a, const B& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 300'005, INF = 0X3F3F3F3F;

class DisjointSetUnion {
private:

    mutable vector<int> roots;

public:

    DisjointSetUnion() {};

    void resize(const int n) {
        roots.resize(n, -1);
    }

    int getRoot(const int x) const {
        return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
    }

    int unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return x;
        if (roots[x] > roots[y])
            swap(x, y);
        roots[x] += roots[y];
        return roots[y] = x;
    }

};

signed roots[MAX_N], minimumDistance[MAX_N];
vector<int> graph[MAX_N];
DisjointSetUnion dsu;
int N, Q, c[MAX_N];

void runBFS() {
    queue<int> q;

    minimumDistance[c[1]] = 0;
    q.push(c[1]);

    for (; !q.empty(); q.pop()) {
        const int &x = q.front();
        for (const int &y : graph[x])
            if (minimize(minimumDistance[y], minimumDistance[x] + 1))
                q.push(y);
    }
}

int main() {
    bool firstTypeOperationPhase = false, sourceFlag = false;

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> Q;

    dsu.resize(N + 1);

    for (int i = 1; i <= N; ++i) {
        cin >> c[i];
        minimumDistance[i] = INF;
        int &root = roots[c[i]];
        root = (root ? dsu.unite(root, i) : i);
    }

    for (int q = 1, t = 0, x = 0, y = 0; q <= Q; ++q) {
        cin >> t >> x >> y;
        if (t == 2) {
            int &rootX = roots[x];
            if (rootX == 0)
                continue;
            int &rootY = roots[y];
            rootY = (rootY ? dsu.unite(rootX, rootY) : rootX);
            rootX = 0;
            continue;
        }
        if (!firstTypeOperationPhase) {
            for (int i = 1; i <= N; ++i)
                if (roots[i])
                    c[dsu.getRoot(roots[i])] = i;
            for (int i = 1; i <= N; ++i)
                c[i] = c[dsu.getRoot(i)];
            firstTypeOperationPhase = true;
        }
        if (roots[x] == 0 || roots[y] == 0)
            continue;
        graph[x].push_back(y);
        graph[y].push_back(x);
        if (x == c[1] && y == c[1])
            sourceFlag = true;
    }

    runBFS();

    cout << 0 << ' ';

    for (int i = 2; i <= N; ++i) {
        if (c[i] != c[1]) {
            cout << ((minimumDistance[c[i]] < INF) ? minimumDistance[c[i]] : (-1)) << ' ';
            continue;
        }
        cout << (sourceFlag ? 1 : ((!graph[c[1]].empty()) ? 2 : (-1))) << ' ';
    }

    cout << '\n';

    return 0;
}

:::

### Subtask 4

:::spoiler Ý tưởng

- Việc xử lý trên đồ thị xây dựng như ở [subtask $1$](https://hackmd.io/2Fp-DrFwSa2vuYYHOOW0UQ?both=#Subtask-1) yêu cầu độ phức tạp thời gian lớn bởi đồ thị sẽ chứa rất nhiều cạnh ($O(Q \cdot N^2)$ cạnh). Tuy nhiên, ta nhận thấy rằng các thao tác này chỉ phụ thuộc vào mối quan hệ giữa các tập đỉnh chứ không bắt buộc phải giữa từng cặp đỉnh cụ thể. Do đó, ta có thể tìm cách xây dựng một đồ thị nén, trong đó:
- Khoảng cách ngắn nhất từ đỉnh $1$ đến cách đỉnh khác trong đồ thị gốc vẫn được giữ nguyên trong đồ thị mới này.
- Số lượng cạnh không quá lớn.

- Để xây dựng một đồ thị có ít cạnh hơn nhưng vẫn giữ nguyên khoảng cách ngắn nhất, ta có thể tạo các đỉnh đại diện cho từng tập đỉnh cùng màu (ở một thời điểm).
>[!Note] Chúng ta có thể xem xét một đồ thị ví dụ như sau để dễ hình dung ý tưởng hơn.
> 
> Giả sử ta cần thêm các cạnh nối từ tất cả các đỉnh xanh đến tất cả các đỉnh cam. Mục tiêu của ta không phải là tạo đủ mọi cạnh giữa hai tập, mà chỉ cần đảm bảo rằng tồn tại đường đi có độ dài 1 từ tập xanh đến tập cam.
> Thay vì thêm $r \times b$ cạnh (với $r$ là số đỉnh xanh và $b$ là số đỉnh cam), ta tạo hai đỉnh mới:
> - Đỉnh $B$ với ý nghĩa là với mọi đỉnh có thể đến được từ đỉnh $B$ thì cũng có thể đến được từ các đỉnh xanh tới tổng trọng số không đổi.
> - Đỉnh $R$ với ý nghĩa là với mọi đỉnh có thể đến được đỉnh $R$ thì cũng có thể đến được các đỉnh cam tới tổng trọng số không đổi.
> Sau đó:
> - Thêm các cạnh có trọng số $0$ từ mỗi đỉnh xanh tới $B$, và từ $R$ tới mỗi đỉnh cam.
> - Thêm một cạnh có trọng số $1$ từ $B$ tới $R$.
> Khi đó, đi từ một đỉnh xanh $x$ tới một đỉnh cam $y$ tương đương với đi qua đường $x \rightarrow B \rightarrow R \rightarrow y$ có tổng trọng số $1$.
> Bằng cách nén như vậy, số cạnh giảm từ $r \times b$ xuống còn $r + b + 1$.

- Mở rộng từ ý tưởng như trên, với mỗi tập đỉnh tại một điểm trong quá trình thực hiện các thao tác, ta sẽ tạo hai đỉnh đi và về (tương tự đỉnh $B$ và $R$ trong ví dụ trên) để đại diện cho tập đó. Cụ thể hơn:
- Với mỗi màu và tập đỉnh của nó ở thời điểm ban đầu (khi chưa thực hiện bất kì thao tác nào trong danh sách), ta tạo hai đỉnh cùng cạnh trọng số $0$ tương ứng (như ví dụ trên).
- Khi ta xử lý thao tác loại $2$, ta (có thể) sẽ có một tập đỉnh mới. Trong trường hợp đó, ta cũng tạo hai đỉnh mới *đại diện cho tập đỉnh của màu sau khi được gộp lại* và thực hiện nối như sau:
- Ta nối các đỉnh đi của hai tập cũ đến đỉnh đi mới với trọng số $0$.
- Ta nối đỉnh về mới đến các đỉnh về của hai tập cũ với trọng số $0$.
- Khi ta xử lý thao tác loại $1$, ta chỉ cần thêm cạnh trọng số $1$ giữa đỉnh đến và đỉnh đi của các tập đỉnh được xem xét trong thác tác (ta sẽ thêm tối đa hai cạnh bởi cạnh bởi cạnh trong đồ thị gốc là vô hướng).


- Sau khi ta dựng xong đồ thị (sau khi xử lý xong hết các thao tác trong danh sách), để tìm đường đi ngắn nhất từ đỉnh $1$ đến các đỉnh còn lại, ta có thể sử dụng thuật toán [BFS 0-1](https://cp-algorithms.com/graph/01_bfs.html) bởi các cạnh của đồ thị có trọng số $0$ hoặc $1$ (hoặc thuật toán [Dijkstra](https://cp-algorithms.com/graph/dijkstra.html) nhưng với độ phức tạp lớn hơn).

>[!Note]
> Ý tưởng cho subtask này có nhiều điểm tương đồng với cách xây dựng [Kruskal Reconstruction Tree](https://usaco.guide/plat/kruskal-tree?lang=cpp).

:::

:::spoiler Độ phức tạp

- Độ phức tạp về thời gian của ý tưởng nêu trên là $O(N + Q)$
- Việc dựng đồ thị có độ phức tạp $O(N + Q)$ bởi:
- Khi dựng đỉnh mới và cạnh ở thời điểm ban điểm, ta sẽ thêm $C$ đỉnh và $2 \cdot N$ cạnh với $C$ là số màu phân biệt ban đầu ($1 \leq C \leq N$; với mỗi đỉnh ban đầu, ta sẽ thêm hai cạnh mới).
- Với mỗi thao tác loại $2$, ta thêm tối đa hai đỉnh và bốn cạnh. Ta có $O(Q)$ thao tác loại $2$.
- Với mỗi thao tác loại $1$, ta thêm tối đa hai cạnh. Ta có $O(Q)$ thao tác loại $1$.
- Thuật toán [BFS 0-1](https://wiki.vnoi.info/algo/graph-theory/bfs-01) có độ phức tạp $O(N + Q)$ vì đồ thị được dựng lên có $O(N + Q)$ đỉnh và cạnh (nếu ta sử dụng thuật toán [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm), độ phức tạp sẽ là $O((N + Q)\log(N + Q) + N + Q)$).

- Tương tự, ý tưởng nêu trên có độ phức tạp về bộ nhớ là $O(N + Q)$.

:::

:::spoiler Code minh họa

#include <bits/stdc++.h>

using namespace std;

template<class A, class B>
bool maximize(A &a, const B& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class A, class B>
bool minimize(A &a, const B& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 3E5 + 5, MAX_VERTEX_COUNT = 1E6 + 6, INF = 0X3F3F3F3F;

int N, Q, c[MAX_N];
bool minimized[MAX_VERTEX_COUNT];
pair<int, int> vertexPairs[MAX_N];
vector<pair<int, bool> > graph[MAX_VERTEX_COUNT];
signed vertexCount, minimumDistance[MAX_VERTEX_COUNT];

void runBFS() {
    deque<int> q;

    for (int i = 2; i <= vertexCount; ++i)
        minimumDistance[i] = INF;

    q.push_back(1);

    for (; !q.empty();) {
        const int x = q.front();
        q.pop_front();
        if (minimized[x])
            continue;
        minimized[x] = true;
        for (const auto &[y, w] : graph[x])
            if (minimize(minimumDistance[y], minimumDistance[x] + w)) {
                if (w)
                    q.push_back(y);
                else
                    q.push_front(y);
            }
    }
}

int main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> Q;

    vertexCount = N;

    for (int i = 1; i <= N; ++i) {
        cin >> c[i];
        auto &[source, sink] = vertexPairs[c[i]];
        if (source <= 0) {
            source = ++vertexCount;
            sink = ++vertexCount;
        }
        graph[i].emplace_back(source, 0);
        graph[sink].emplace_back(i, 0);
    }

    for (int q = 1, t = 0; q <= Q; ++q) {
        cin >> t;
        if (t == 1) {
            int x = 0, y = 0;
            cin >> x >> y;
            const auto &[sourceX, sinkX] = vertexPairs[x];
            const auto &[sourceY, sinkY] = vertexPairs[y];
            if (sourceX && sinkY) {
                graph[sourceX].emplace_back(sinkY, 1);
                graph[sourceY].emplace_back(sinkX, 1);
            }
        } else {
            int u = 0, v = 0;
            cin >> u >> v;
            const auto [sourceU, sinkU] = vertexPairs[u];
            const auto [sourceV, sinkV] = vertexPairs[v];
            auto &[source, sink] = vertexPairs[v];
            vertexPairs[u] = make_pair(0, 0);
            source = ++vertexCount;
            sink = ++vertexCount;
            graph[sourceU].emplace_back(source, 0);
            graph[sourceV].emplace_back(source, 0);
            graph[sink].emplace_back(sinkU, 0);
            graph[sink].emplace_back(sinkV, 0);
        }
    }

    runBFS();

    for (int i = 1; i <= N; ++i)
        cout << ((minimumDistance[i] < INF) ? minimumDistance[i] : (-1)) << ' ';

    cout << '\n';

    return 0;
}

:::

## Phụ Lục

:::spoiler Trình Chấm (tự viết)

import time
import shutil
import random
import subprocess
from abc import ABC
from pathlib import Path
from typing import List, Tuple

class TestGenerator(ABC):

    MIN_N: int = 1
    MAX_N: int = 300_000
    MIN_Q: int = 1
    MAX_Q: int = 300_000

    def __init__(self):
        self.N: int = 0
        self.Q: int = 0
        self.c: List[int] = []
        self.operations: List[Tuple[int, int, int]] = []
        self.generate()

    def generate(self):
        self.N = random.randint(self.MIN_N, self.MAX_N)
        self.Q = random.randint(self.MIN_Q, self.MAX_Q)
        self.c = [random.randint(1, self.N) for _ in range(self.N)]
        self.operations = self._generate_operations()

    def _generate_operations(self) -> List[Tuple[int, int, int]]:
        return [self._generate_random_operation(random.randint(1, 2)) for _ in range(self.Q)]
    
    def _generate_random_operation(self, operation_type: int) -> Tuple[int, int, int]:
        return (operation_type, random.randint(1, self.N), random.randint(1, self.N))
    
    def write_to_file(self, filename: str) -> None:
        path = Path(filename)
        path.parent.mkdir(parents = True, exist_ok = True)
        with path.open('w') as f:
            f.write(f"{self.N} {self.Q}\n")
            f.write(" ".join(map(str, self.c)) + "\n")
            for t, x, y in self.operations:
                f.write(f"{t} {x} {y}\n")

class Subtask1TestGenerator(TestGenerator):
    MAX_N = 100
    MAX_Q = 100

class Subtask2TestGenerator(TestGenerator):
    def _generate_operations(self) -> List[Tuple[int, int, int]]:
        return [self._generate_random_operation(1) for _ in range(self.Q)]

class Subtask3TestGenerator(TestGenerator):
    def _generate_operations(self) -> List[Tuple[int, int, int]]:
        second_type_operation_count = random.randint(0, self.Q)
        return [self._generate_random_operation(2 if i < second_type_operation_count else 1) for i in range(self.Q)]

class Subtask4TestGenerator(TestGenerator):
    pass

class Validator:

    TIME_LIMIT_IN_SECONDS = 1
    VERDICTS = ["AC", "WA", "TLE", "RE"]

    def __init__(self, tested_program_path: str, correct_program_path: str):
        self.tested_program = Path(tested_program_path)
        self.correct_program = Path(correct_program_path)
        for program in (self.tested_program, self.correct_program):
            if not program.exists():
                raise FileNotFoundError(f"Program not found: {program}")
            if not program.suffix.lower() == '.exe':
                raise ValueError(f"Program must be an .EXE file: {program}")

    def run_program(self, program_path: Path, input_file: Path, output_file: Path) -> Tuple[str, float, bool]:
        program_directory = program_path.parent
        destination_input = program_directory / "input.INP"
        shutil.copy(input_file, destination_input)
        destination_output = program_directory / output_file.name
        if destination_output.exists():
            destination_output.unlink()
        start_time = time.time()
        try:
            process = subprocess.run(
                [str(program_path)],
                stdout=subprocess.PIPE,
                stderr=subprocess.PIPE,
                timeout=self.TIME_LIMIT_IN_SECONDS,
                text=True,
                cwd=str(program_directory)
            )
            execution_time = time.time() - start_time

            if process.returncode != 0:
                return "RE", execution_time, False

            if destination_output.exists():
                with destination_output.open('r') as f:
                    output = f.read().strip()
            else:
                output = process.stdout.strip()

            return "OK", execution_time, True, output

        except subprocess.TimeoutExpired:
            return "TLE", self.TIME_LIMIT_IN_SECONDS, False, ""
        except Exception as e:
            return "RE", time.time() - start_time, False, str(e)
        return "IE", time.time() - start_time, False, ""

    def compare_outputs(self, tested_output: str, correct_output: str) -> str:
        tested_lines = [line.strip() for line in tested_output.splitlines() if line.strip()]
        correct_lines = [line.strip() for line in correct_output.splitlines() if line.strip()]
        
        if tested_lines == correct_lines:
            return "AC"
        return "WA"
    
    def validate_test(self, input_file: str) -> Tuple[str, float]:
        input_path = Path(input_file)
        input_directory = input_path.parent

        correct_verdict, correct_time, correct_success, correct_output = self.run_program(
            self.correct_program, input_path, self.correct_program.parent / "output.OUT"
        )
        if not correct_success:
            return f"Correct program failed: {correct_verdict}", correct_time
        
        answer_file = input_directory / "answer.txt"
        with answer_file.open('w') as f:
            f.write(correct_output)

        tested_verdict, tested_time, tested_success, tested_output = self.run_program(
            self.tested_program, input_path, self.tested_program.parent / "output.OUT"
        )
        if not tested_success:
            return tested_verdict, tested_time
        
        output_file = input_directory / "output.out"
        with output_file.open('w') as f:
            f.write(tested_output)

        verdict = self.compare_outputs(tested_output, correct_output)
        return verdict, tested_time

SUBTASK_GENERATORS = [
    Subtask1TestGenerator,
    Subtask2TestGenerator,
    Subtask3TestGenerator,
    Subtask4TestGenerator,
]

SUBTASK_TEST_PERCENTAGES = [20, 30, 20, 30]

TOTAL_TEST_COUNT = 100

if __name__ == "__main__":
    random.seed(20251004)
    subtask_test_counts = [TOTAL_TEST_COUNT * percentage // 100 for percentage in SUBTASK_TEST_PERCENTAGES]
    validator = Validator(
        tested_program_path = "programs/tested_program/main.exe",
        correct_program_path = "programs/correct_program/main.exe",
    )
    overall_summary = {}
    for verdict in Validator.VERDICTS:
        overall_summary[verdict] = 0
    for subtask_index in range(len(SUBTASK_GENERATORS)):
        generator = SUBTASK_GENERATORS[subtask_index]()
        subtask_summary = {}
        for verdict in Validator.VERDICTS:
            subtask_summary[verdict] = 0
        for test_index in range(subtask_test_counts[subtask_index]):
            filename = f"tests/subtask{subtask_index + 1:02d}/test{test_index + 1:02d}/input.INP"
            generator.generate()
            generator.write_to_file(filename)
            verdict, tested_time = validator.validate_test(filename)
            subtask_summary[verdict] += 1
            print(f"Subtask {subtask_index + 1}, Test {test_index + 1}: Verdict = {verdict}, Time = {tested_time:.3f}s")
        print(f"Subtask {subtask_index + 1} Summary:")
        for verdict, count in subtask_summary.items():
            overall_summary[verdict] += count
            print(f"\t{verdict}: {count} tests")
    print("Overall Summary:")
    for verdict, count in overall_summary.items():
        print(f"\t{verdict}: {count} tests")

:::