Liên Minh

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

1. 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\le V-1$ cho hầu hết thành phần. Nhưng nếu xảy ra: trả về $0$.
2. Đỉ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

1. Đọc đồ thị $N$ đỉnh $M$ cạnh (vô hướng).
2. 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.
3. 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.
4. In đáp án modulo ${10}^9+7$.

Độ phức tạp

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