（无根树转有根树）吝啬的国度_Youpeng

NYOJ-吝啬的国度-20

一道经典的无根树转有根树模板题。

模板：

#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1000;
int n, p[MAXN];
vector<int> G[MAXN];
//第一种dfs写法:
//不需要对对p进行memset；
void dfs(int u, int fa) {//递归转化为以u为根的子树，u的父亲为fa
	int d = G[u].size(); //节点u的相邻点的个数
	for(int i = 0; i < d; ++i) { //循环遍历跟这个节点相连接的d个节点。
		int v = G[u][i];       //节点u的第i个相邻点v
		if(fa != v) dfs(v, p[v] = u);  //把v的父亲节点设为u，然后递归转化为以v为根的子树
		//一定要判断v是否和其父亲节点相等！
	}
}
//第二种dfs写法：用pre代替p；
//之前要对pre[maxn] 进行 memset(pre,0,sizeof(pre));
void dfs(int s)
{
    int d=G[u].size();
    for(int i=0; i < d;i++)
    {
        int v=G[u][i];
        if(pre[v])
            continue;
        pre[v]=s;
        dfs(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;
}#i