题解+思路（bfs）

思路

这个题目的关键就是利用 bfs 的特性：从上至下依次遍历节点。

因此从根节点开始遍历，如果和该有边相连的的节点没有被访问过，就说明这个节点是该节点的子节点。

就是说和该节点有边相连的节点有两种：
①父节点 ②子节点

而父节点必定于当前节点先被访问过（逐层访问），因此一定被标记过。此时寻找未被标记过的就是当前节点的子节点，直接标记。

代码

#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> a[500];
bool vis[500]; //必要的，因为仅记录有边相连，无法确定父子关系
queue<int> q;
map<int,int> fa; //存储每个节点的父节点

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;

        cin>>x>>y;

        a[x].push_back(y);
        a[y].push_back(x);
        //由于不知道谁是谁的父节点，此处仅记录有边相连
    }

    q.push(1);
    vis[1]=1;
    //初始化队列和vis数组

    while(!q.empty()){
        int now=q.front();
        q.pop(); //取出当前节点

        for(int i=0;i<a[now].size();i++){ //遍历和当前节点有边相连的节点
            int x=a[now][i];
            
            if(vis[x]==0){
            //如果没有访问过这个节点，证明这个节点的层数在当前节点之下，为当前节点的子节点
                q.push(x);
                fa[x]=now; //这个节点的父节点就为当前节点
                vis[x]=1;
            }
        }
    }

    for(int i=2;i<=n;i++){
        cout<<fa[i]<<' ';
    }

    return 0;
}