无向图节点父亲输出-深度优先搜索C++实现

思路：

1. 构建邻接表表示图。
2. 从节点1开始进行深度优先搜索，记录每个节点的父节点。使用一个数组parent[]来存储每个节点的父节点。
3. 在深度优先搜索中，对于当前节点u的每个相邻节点v，如果v的父节点还未确定，则将v的父节点设置为u，并递归地对v进行深度优先搜索。
4. 最后输出每个节点的父节点。

代码实现：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100;  // 最大节点数
vector<int> adj[MAXN]; // 邻接表表示图
int parent[MAXN];      // 存储每个节点的父节点

void dfs(int u) {
    for (int v : adj[u]) {
        if (parent[v] == -1) {  // 如果v的父节点还未确定
            parent[v] = u;     // 将v的父节点设置为u
            dfs(v);            // 递归地对v进行深度优先搜索
        }
    }
}

int main() {
    int n;
    cin >> n;

    // 初始化父节点数组
    for (int i = 1; i <= n; i++) {
        parent[i] = -1;
    }

    // 构建邻接表表示图
    for (int i = 1; i <= n; i++) {
        int m;
        cin >> m;
        for (int j = 0; j < m; j++) {
            int v;
            cin >> v;
            adj[i].push_back(v);
        }
    }

    // 从节点1开始进行深度优先搜索
    parent[1] = 1;
    dfs(1);

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

    return 0;
}

复杂度分析： 构建邻接表的时间复杂度为O(n+m)，其中n为节点数，m为边数。深度优先搜索的时间复杂度为O(n+m)。因此，总的时间复杂度为O(n+m)。空间复杂度为O(n)。