--- author: nguyencter tags: QN title: QN Solution --- $\Huge\text{QN Solution}$ ------- :::info 🔗 Links: [Đề bài](https://drive.google.com/file/d/1YwqnQYBHi2LSVC4-UpPiCTytoScuplbl/view?usp=sharing) 📌 Tags: `dfs` `brute force` ✍️ Writer: nguyencter 📋 Content: [TOC] ::: ----- ## Giới Thiệu Đề Bài Đồ thị khối n chiều là đồ thị có $2^n$ đỉnh, mỗi đỉnh được biểu diễn bằng một xâu nhị phân độ dài n. Hai đỉnh có cạnh nối nếu xâu nhị phân biểu diễn của hai đỉnh khác nhau đúng 1 bit. **Yêu cầu :** Tìm đường đi Hamilton trên đồ thị trên sau khi xóa 1 đỉnh khỏi đồ thị ----- ## Thuật toán $\Large N \leq 20$ Ta có thể thấy được đồ thị ban đầu là đồ thị liên thông chứa chu trình và mỗi đỉnh đều có n cạnh. Mà đường đi Hamilton là đường đi xuất phát tại một đỉnh, đi qua tất cả các đỉnh, mỗi đỉnh qua đúng một lần. Vì vậy khi xóa đỉnh $x$ thì đỉnh kề của $x$ sẽ là đầu mút của đường đi Hamilton. Ta duyệt các đỉnh kề với $x$ và kiểm tra đỉnh này đã được thăm hay chưa, nếu chưa thì tiếp tục duyệt các đỉnh kề của đỉnh này. In ra các đỉnh theo thứ tự được thăm. Đpt $O(n*2^n)$. ---- Tham khảo code ở [đây](https://github.com/nguyencter/CODE/blob/main/QN.cpp)