寻找父节点

搜索树的开端

这是一道让你找父节点的题,给了你一颗无向树（当无向图），去找父节点

不要想太简单

我们可以用邻接表存储这棵树

    for(int i=1;i<a;i++){
        int c,d;
        cin>>c>>d;
        tree[c].push_back(d);
        tree[d].push_back(c);//当无向图
    }

接下来遍历图（可以用bfs，有人写了，我用的是dfs）

void dfs(int a){
    vis[a]=true;//已访问，vis标记
    int c=tree[a].size();   
    for(int i=0;i<c;i++){//搜索有连边的节点 
        if(vis[tree[a][i]]==false){//未访问
            fa[tree[a][i]]=a;//标记tree[a][i]的父亲
            dfs(tree[a][i]);//搜索a的儿子
        }
    }
    return; //好习惯
}

最后输出便可
代码如下：

#include<iostream>
#include<vector>
using namespace std;
bool vis[505]={false};
int dir[2]={1,-1};
vector<int>tree[505];
int fa[505];
void dfs(int a){
    vis[a]=true;//已访问
    int c=tree[a].size();
 //   cout<<"树"<<a<<"有"<<c<<"个节点"<<endl;
    for(int i=0;i<c;i++){//搜索有连边的节点 
        if(vis[tree[a][i]]==false){//未访问
            fa[tree[a][i]]=a;//标记tree[a][i]的父亲
            dfs(tree[a][i]);//搜索a的儿子
        }
    }
    return; 
}
int main(){
    int a;
    cin>>a;
    for(int i=1;i<a;i++){
        int c,d;
        cin>>c>>d;
        tree[c].push_back(d);
        tree[d].push_back(c);//当无向图
    }
    dfs(1);
    for(int i=2;i<=a;i++){
        cout<<fa[i]<<' ';
    }
    return 0;//好习惯
}

感谢智齿！