# VNOI - Coding Challenge #1 - Đường đi

## Phân tích đề bài
### Đề bà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ị.

### Phân tích
Ta nhận thấy rằng độ phức tạp của bài này sẽ là độ phức tạp của phần dựng đồ thị cộng với độ phức tạp của phần tìm đường đi ngắn nhất từ đỉnh $1$, mà độ phức tạp của việc tìm đường đi lại phụ thuộc vào số lượng đỉnh và cạnh trong đồ thị.

Vì vậy, vấn đề chính của bài này là làm sao để dựng đồ thị với số đỉnh và cạnh ít nhất mà vẫn thỏa mãn yêu cầu bài toán. Còn việc tìm đường đi ngắn nhất thì ta sẽ sử dụng thuật toán **BFS, BFS 0-1, Dijkstra** tùy vào cách ta dựng đồ thị.

## Subtask 1: $N, Q \leq 100$

Ta sẽ mô phỏng toàn bộ các thao tác thêm cạnh và đổi màu các đỉnh với mỗi loại thao tác. Giả sử đồ thị ban đầu là đồ thị $G$ không trọng số và chưa được thêm cạnh nào, ta sẽ tiến hành xử lý như sau:

- Với thao tác `1 x y`: Duyệt tất cả các cặp $(i, j)$ thỏa mãn $c_i = x$ và $c_j = y$, với mỗi cặp ta thực hiện thêm một cạnh hai chiều $(i, j)$ vào đồ thị $G$
- Với thao tác `2 u v`: Duyệt qua toàn bộ các đỉnh $i$ từ $1 \to n$, với các đỉnh thỏa mãn $c_i = u$, ta gán lại $c_i = v$

Số lượng cạnh sẽ lên tới $n^2$. Đồ thị này không có trọng số nên ta sử dụng thuật toán **BFS** để tìm đường đi ngắn nhất từ đỉnh $1$ đến các đỉnh khác.

Độ phức tạp: $O(q \times n^2)$

## Subtask 2: Chỉ có thao tác loại $1$

Với mỗi đỉnh $i$ từ $1 \to n$, mỗi đỉnh sẽ có một màu cố định (vì không có thao tác loại $2$).

Xét thao tác `1 x y`, gọi $X, Y$ lần lượt là tập các đỉnh có màu $x, y$. Ta cần thêm các cạnh vào đồ thị sao cho các tính chất sau được thỏa mãn:

- Tổng trọng số của đường đi ngắn nhất khi đi từ một đỉnh thuộc tập $X$ đến một đỉnh thuộc tập $Y$ và ngược lại khi chỉ sử dụng các cạnh mới thêm vào là $1$
- Tổng trọng số của đường đi ngắn nhất khi đỉnh bắt đầu và đỉnh kết thúc đều thuộc tập $X$ hoặc tập $Y$ khi chỉ sử dụng các cạnh mới thêm vào là $2$

Để xử lý việc thêm cạnh, với mỗi tập đỉnh $X$ có màu $x$, ta định nghĩa thêm hai đỉnh phụ:

- $in_X$: Đỉnh đại diện cho việc đi vào các đỉnh trong tập $X$, với mỗi đỉnh $i \in X$, ta thêm một cạnh có hướng có trọng số $(in_X, i, 0)$ vào đồ thị
- $out_X$: Đỉnh đại diện cho việc đi ra từ các đỉnh trong tập $X$, với mỗi đỉnh $i \in X$, ta thêm một cạnh có hướng có trọng số $(i, out_X, 0)$ vào đồ thị

Với mỗi truy vấn `1 x y`, để nối các đỉnh của tập $X$ và tập $Y$ với nhau, ta thêm lần lượt hai cạnh có hướng có trọng số là $(out_X, in_Y, 1)$ và $(out_Y, in_X, 1)$ vào đồ thị.

Giả sử tập $X = \{1, 2, 3\}$ với hai đỉnh phụ $7, 8$ và tập $Y = \{4, 5, 6\}$ với hai đỉnh phụ $9, 10$, ta sẽ nối cạnh như hình dưới đây.


Tổng số lượng đỉnh và số lượng cạnh không vượt quá $3 \times n + 2 \times q$. Đồ thị chỉ có trọng số $0$ và $1$ nên ta sử dụng thuật toán **BFS 0-1** để thực hiện việc tìm đường đi ngắn nhất.

Độ phức tạp: $O(n + q)$

## Subtask 3: Tất cả thao tác loại $2$ xuất hiện trước thao tác loại $1$

Xét thao tác `2 u v`, gọi $U$ và $V$ lần lượt là tập các đỉnh có màu $u$ và $v$, thao tác này sẽ gộp $U$ và $V$ lại thành chung một tập các đỉnh có màu $v$ và số lượng tập phân biệt sẽ giảm đi $1$, hoặc giữ nguyên nếu tập $U$ hoặc $V$ không có đỉnh nào.

Ta sẽ tiền xử lý tất cả các thao tác loại $2$ bằng cách sử dụng cấu trúc dữ liệu **DSU**, với mỗi tập ta lưu hai giá trị $root, color$ lần lượt là đỉnh gốc và màu của tập đó. Với thao tác `2 u v`, ta nối gốc của hai tập $U$ và $V$ lại với nhau và gán lại $color = v$, sau khi tiền xử lý xong các thao tác loại $2$ thì ta sẽ làm như Subtask 2.

Độ phức tạp: $O(n \times \log_{2}(n) + q)$

## Subtask 4: $N, Q \leq 3 \times 10^5$

Kết hợp ý tưởng của Subtask 2 và Subtask 3, ta sẽ xử lý thao tác loại $1$ song song với thao tác loại $2$ bằng cấu trúc dữ liệu **DSU** cùng với các đỉnh phụ. Với mỗi tập $X$ ta lưu bốn giá trị $root_X, color_X, in_X, out_X$ lần lượt là đỉnh gốc, màu, đỉnh đi vào và đỉnh đi ra của tập $X$. Với từng loại thao tác ta sẽ xử lý như sau:

- Thao tác `1 x y`: Gọi $X$ và $Y$ lần lượt là tập các đỉnh có màu $x$ và $y$, ta thêm hai cạnh có hướng có trọng số $(out_X, in_Y, 1)$ và $(out_Y, in_X, 1)$ vào đồ thị
- Thao tác `2 u v`: Gọi $U$ và $V$ lần lượt là tập các đỉnh có màu $u$ và $v$, để gộp tập $U$ vào $V$, ta tạo thêm hai đỉnh phụ lần lượt là $A$ và $B$ đại diện cho đỉnh vào và đỉnh ra của hai tập $U$ và $V$ sau khi gộp lại với nhau, sau đó thêm lần lượt bốn cạnh có hướng có trọng số $(out_U, A, 0)$, $(out_V, A, 0)$, $(B, in_U, 0)$ và $(B, in_V, 0)$ sau đó lần lượt gán lại $in = A$, $out = B$ và $color = v$ cho tập mới sau khi gộp

Tổng số lượng đỉnh và số lượng cạnh không vượt quá $5 \times n + 2 \times q$. Sử dụng **BFS 0-1** để tìm đường đi ngắn nhất từ đỉnh $1$.

Độ phức tạp: $O(n \times \log_{2}(n) + q)$