C++ 实现无向图节点父亲查找算法

以下是使用 C++ 实现的代码，用于查找无向图中每个节点的父亲节点：

#include <iostream>
#include <vector>

using namespace std;

vector<int> findParents(int n, vector<pair<int, int>>& edges) {
    vector<int> parents(n+1, 0); // 存储每个节点的父亲
    vector<vector<int>> graph(n+1); // 存储图的邻接表表示

    // 构建图的邻接表
    for(auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<bool> visited(n+1, false); // 标记节点是否被访问

    // 深度优先搜索
    function<void(int)> dfs = [&](int node) {
        visited[node] = true;
        for(int neighbor : graph[node]) {
            if(!visited[neighbor]) {
                parents[neighbor] = node;
                dfs(neighbor);
            }
        }
    };

    // 从节点1开始深度优先搜索
    dfs(1);

    // 输出每个节点的父亲
    vector<int> result(n+1);
    for(int i = 1; i <= n; i++) {
        if(parents[i] == 0) {
            result[i] = i; // 没有父亲，输出自己
        } else {
            result[i] = parents[i];
        }
    }

    return result;
}

int main() {
    int n; // 节点个数
    cin >> n;

    vector<pair<int, int>> edges; // 存储边的信息
    for(int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        edges.push_back({u, v});
    }

    vector<int> parents = findParents(n, edges);

    // 输出每个节点的父亲
    for(int i = 1; i <= n; i++) {
        cout << parents[i] << ' ';
    }
    cout << endl;

    return 0;
}

输入示例：

5
1 2
1 3
2 4
3 5

输出示例：

1 1 1 2 3