无向图DFS环检测代码失效原因咨询（SPOJ PT07Y题）

Hey, let's break down why your approach isn't working for the PT07Y problem (checking if an undirected graph is a tree—i.e., acyclic and connected). You've got two key flaws in your logic that are causing incorrect results:

Undirected graphs have bidirectional edges—so if you traverse from node u to its neighbor v, v's adjacency list will always include u. When you're doing DFS, hitting a visited node doesn't automatically mean there's a cycle—you need to check if that visited node is the parent of the current node (the one you came from).

For example, take a simple tree with two nodes A and B connected by an edge. When you start DFS at A, you mark it as visited, then move to B. When you check B's neighbors, you'll see A (already visited). Your code would flag this as a cycle, but this is just the reverse of the edge you took to get to B—it's not a cycle at all.

Once you've traversed a connected component of the graph, all nodes in that component are marked as visited, and you don't need to process them again. Resetting the visited array causes three big issues:

• Redundant work: You'll re-traverse nodes you've already checked, wasting time.
• Incorrect cycle detection: For a connected tree, when you pick another node to start DFS (after resetting), you'll again hit parent nodes and incorrectly flag them as cycles.
• Broken connectivity check: The PT07Y problem requires the graph to be connected (a tree is a connected acyclic graph). Resetting visited means you can't track how many unique nodes you've traversed, so you can't verify if the entire graph is connected.

The Fix #

Here's the corrected approach for PT07Y:
First, a quick sanity check: if the number of edges isn't exactly n-1 (where n is the number of nodes), the graph can't be a tree—immediately return "NO".

For the DFS part:

• Track the parent of each node to avoid mistaking reverse edges for cycles.
• Don't reset visited—instead, traverse all unvisited nodes (to handle disconnected components) and count how many nodes you've visited to check connectivity.

Here's a simplified pseudocode example:

bool hasCycle(int u, int parent, vector<bool>& visited, vector<vector<int>>& adj) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            if (hasCycle(v, u, visited, adj)) {
                return true;
            }
        } else if (v != parent) {
            // Found a back edge to a non-parent visited node—cycle exists
            return true;
        }
    }
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;
    if (m != n-1) {
        cout << "NO" << endl;
        return 0;
    }
    vector<vector<int>> adj(n+1); // Nodes are 1-indexed
    for (int i=0; i<m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<bool> visited(n+1, false);
    bool cycleExists = hasCycle(1, -1, visited, adj);
    // Check if all nodes are visited (graph is connected)
    bool isConnected = true;
    for (int i=1; i<=n; i++) {
        if (!visited[i]) {
            isConnected = false;
            break;
        }
    }
    if (!cycleExists && isConnected) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

This way, you correctly identify cycles by ignoring parent nodes, and you verify that the entire graph is connected by checking the visited array once after traversal.

内容的提问来源于stack exchange，提问作者Abhi