CSU 1660 K：圖中長度為 K 的簡單環檢測（K≤7 窮舉搜索）

問題描述

無向圖 N≤50, M≤500，查詢是否存在長度恰好為 K (3≤K≤7) 的簡單環（頂點不重複，首尾相連）。

DFS 回溯搜索

K ≤ 7 很小，可從每個頂點出發 DFS 深度限制 K，記錄訪問路徑。
剪枝：
- 當前深度 + 剩餘可達深度 < K → 剪枝。
- 遇到起點且深度 == K → 找到環。
- 避免重複：只從最小編號頂點出發，或要求路徑中頂點遞增（不完全正確，需小心）。

簡潔實現

vector G[55];
bool vis[55], found;
int N, K;

void dfs(int u, int start, int depth) {
    if (found) return;
    if (depth == K) {
        if (u == start) found = true;
        return;
    }
    for (int v : G[u]) {
        if (!vis[v] || (v == start && depth == K-1)) {
            bool wasVis = vis[v];
            vis[v] = true;
            dfs(v, start, depth+1);
            vis[v] = wasVis;
            if (found) return;
        }
    }
}

int main() {
    int T; cin >> T;
    while (T--) {
        int M; cin >> N >> M >> K;
        for (int i=1;i<=N;++i) G[i].clear();
        for (int i=0;i>u>>v; G[u].push_back(v); G[v].push_back(u); }
        found = false;
        for (int i=1; i<=N && !found; ++i) {
            memset(vis, 0, sizeof vis);
            vis[i] = true;
            dfs(i, i, 0);
        }
        cout << (found ? "YES" : "NO") << "\n";
    }
}

優化技巧

• 度數 < 2 的頂點不可能在長度 ≥3 的環上，預先刪除。
• 按度數排序優先搜索高度點。
• 雙向 BFS 相遇檢測環（更複雜，K≤7 不必要）。

複雜度

最壞 O(N * d^(K-1))，d 為平均度。K≤7, N≤50 實際極快。