树结构中节点父节点定义及O(N)级求解方案咨询

Got it, let's break this down properly—since we're dealing with trees up to 3 million nodes, we need a solution that's not just correct but blazing fast (O(N) time) and memory-efficient. Here's how to tackle this using vectors and linear-time traversal:

1. Data Structure Setup #

First, for storing parent nodes: use a vector<int> sized to N+1 (since nodes are numbered 1 to N). This gives us O(1) access to any node's parent, and the contiguous memory of vectors makes it super efficient even for 3M elements. We'll initialize all values to 0, where 0 indicates "no parent" (reserved for the root node).

For the tree itself, we need an adjacency list—again, a vector<vector<int>> sized to N+1. Since trees are undirected, each edge (u, v) gets added to both adj[u] and adj[v].

2. Linear-Time Traversal: BFS (Best for Large Trees) #

Breadth-First Search is perfect here because it's inherently O(N) time, and uses a queue which avoids the stack overflow risk of recursive DFS (critical for trees that might be a long chain of 3M nodes). Here's how it works:

• Pick your root node (in your example, that's node F—just replace the root variable with its number).
• Initialize the queue with the root, and set parent[root] = 0 (marking it as the top of the tree).
• For each node we pull from the queue, iterate through all its adjacent nodes. If an adjacent node hasn't been assigned a parent (i.e., parent[v] == 0 and it's not the root), set its parent to the current node and add it to the queue.

Example Code (C++) #

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    // Speed up input/output for large datasets
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<vector<int>> adj(N + 1);

    // Read N-1 edges
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int root = 1; // Replace with your actual root node (e.g., F's number)
    vector<int> parent(N + 1, 0);
    queue<int> q;
    q.push(root);
    parent[root] = 0;

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        for (int neighbor : adj[current]) {
            // Skip the parent node and uninitialized root
            if (parent[neighbor] == 0 && neighbor != root) {
                parent[neighbor] = current;
                q.push(neighbor);
            }
        }
    }

    // Output results (adjust as needed)
    for (int i = 1; i <= N; ++i) {
        cout << "Node " << i << " → Parent: " << (parent[i] == 0 ? "None" : to_string(parent[i])) << '\n';
    }

    return 0;
}

3. Alternative: Iterative DFS #

If you prefer Depth-First Search, use an iterative approach (no recursion!) to avoid stack overflow. The logic is almost identical—just swap the queue for a stack:

// Iterative DFS replacement for the BFS section
vector<int> parent(N + 1, 0);
stack<int> st;
st.push(root);
parent[root] = 0;

while (!st.empty()) {
    int current = st.top();
    st.pop();

    for (int neighbor : adj[current]) {
        if (parent[neighbor] == 0 && neighbor != root) {
            parent[neighbor] = current;
            st.push(neighbor);
        }
    }
}

4. Critical Optimizations for 3M Nodes #

• Skip the visited array: We use the parent array itself to track visited nodes—if parent[v] != 0, it's already been processed. This saves ~3MB of memory (no need for a vector<bool>).
• Fast I/O: For 3M nodes, using default cin/cout will be too slow. Add ios::sync_with_stdio(false); cin.tie(nullptr); to disable synchronization with C stdio, or use scanf/printf instead.
• Heap memory only: Never create large arrays on the stack—vectors automatically use heap memory, which can handle the size of 3M elements easily.

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