无根树转化为有根数

本文主要是介绍无根树转化为有根数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

输入n个节点的无根树的各条边，指定一个节点为根，将无根树转为有根树。

伪代码：

int fa[maxn];   //每个节点的父亲 
vector<int> G[maxn];
int dfs(int f)      //无根树化为有根树 
{int i;for(i=0; i<G[f].size(); i++){if(fa[f] != G[f][i]){fa[G[f][i]] = f; dfs(G[f][i]);}}
}

代码：

#include <iostream>
#include <vector>
using namespace std;const int MAXN = 1000;
int n, p[MAXN];
vector<int> G[MAXN];void dfs(int u, int fa) {   //递归转化为以u为根的子树，u的父亲为faint d = G[u].size();        //节点u的相邻点的个数for(int i = 0; i < d; ++i) {    //循环遍历跟这个节点相连接的d个节点。int v = G[u][i];       //节点u的第i个相邻点vif(fa != v) dfs(v, p[v] = u);  //把v的父亲节点设为u，然后递归转化为以v为根的子树//一定要判断v是否和其父亲节点相等！}
}int main() {cin >> n;for(int i = 0; i < n-1; i++) {   //输入n-1条边int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}int root;   cin >> root;    //指定根节点。p[root] = -1;   //设定根节点的父亲节点为-1，代表根节点没有父亲节点。dfs(root, -1);for(int i = 0; i < n; ++i) {cout << p[i] << endl;}return 0;
}

这篇关于无根树转化为有根数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---