寻找父节点

ccj123

2025-02-03 09:21:07

发布于：上海

6阅读

0回复

0点赞

邻接矩阵

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

int g[110][110];//邻接矩阵
int n;//结点数量
int father[110];
void dfs(int u,int fa){
    father[u] = fa;
    for(int i=1;i<=n;i++){
        if(g[u][i]==1 && i!=fa){
            dfs(i,u);
        }
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n-1;i++){
        int a,b;
        cin>>a>>b;
        g[a][b] = 1;
        g[b][a] = 1;
    }
    dfs(1,-1);
    for(int i=2;i<=n;i++){
        cout<<father[i]<<" ";
    }
    return 0;
}

邻接表

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

vector<int> g[110];
int n;//结点数量
int father[110];
void dfs(int u,int fa){
    father[u] = fa;
    for(int son:g[u]){
        if(son==fa)continue;
        dfs(son,u);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n-1;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,-1);
    for(int i=2;i<=n;i++){
        cout<<father[i]<<" ";
    }
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

邻接矩阵

热门讨论