Hướng dẫn giải của Liên Minh

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Liên Minh

Hướng tiếp cận

Phân tích theo từng thành phần liên thông. Với mỗi thành phần có $V$ đỉnh và $E$ cạnh, số cách gán hợp lệ phụ thuộc vào quan hệ giữa $V$ và $E$ . Nhân kết quả tất cả thành phần lại với nhau (modulo $10^{9} + 7$ ).

Nhận xét quan trọng

Với M<N, tổng số cạnh nhỏ hơn số đỉnh. Mỗi thành phần liên thông chỉ có thể là:
- Cây ( $E = V - 1$ ): có đúng $V$ cách gán hợp lệ (mỗi cạnh trong cây có thể là "cạnh gốc" để gán các đỉnh).
- Unicyclic ( $E = V$ , đúng một chu trình): có đúng $2$ cách gán hợp lệ.
- $E > V$ : không thể xảy ra vì $M < N$ nên $E \leq V - 1$ cho hầu hết thành phần. Nhưng nếu xảy ra: trả về $0$ .
Đỉnh cô lập ( $E = 0, V = 1$ ): là trường hợp đặc biệt của cây với $V = 1$ , nhưng không có cạnh kề để gán, nên không có cách gán — kết quả là $0$ .

Thuật toán

Đọc đồ thị $N$ đỉnh $M$ cạnh (vô hướng).
Với mỗi đỉnh chưa thăm, DFS để tính $V$ (số đỉnh) và $E$ (số cạnh, chia 2 vì mỗi cạnh đếm 2 lần) của thành phần liên thông.
Phân tích thành phần:
- Nếu $E > V$ : in $0$ và kết thúc.
- Nếu $E = V - 1$ (cây): nhân đáp án với $V$ .
- Nếu $E = V$ (unicyclic): nhân đáp án với $2$ .
- Nếu $E < V - 1$ (có đỉnh cô lập): in $0$ và kết thúc.
In đáp án modulo $10^{9} + 7$ .

Độ phức tạp

Thời gian: $O (N + M)$
Bộ nhớ: $O (N + M)$

Bình luận

Không có bình luận tại thời điểm này.