hihoOffer收割练习20题目1

题目1 : 无根数变有根树

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定一棵包含  个节点的无根树，小Hi想知道如果指定其中某个节点  为根，那么每个节点的父节点是谁？

输入

第一行包含一个整数  和 。1 ≤  ≤ 1000, 1 ≤  ≤ 。

以下-1行每行包含两个整数  和 ，代表之间存在一条边。 1 ≤ ,  ≤ 。

输入保证是一棵树。

输出

输出一行包含  个整数，分别代表1~的父节点的编号。对于  的父节点输出0。

样例输入

5 4

1 2

3 1

4 3

5 1

样例输出

3 1 4 0 1

代码如下：

#include <iostream>

#include <vector>

using namespace std;

const int MAXN = 1005;

int n, p[MAXN];

vector<int> G[MAXN];

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是否和其父亲节点相等！

	}

}

int main() {

    int root;

	//cin >> root;

	cin >> n>>root;

	for(int i = 1; i <= n-1; i++) {   //输入n-1条边

		int u, v;

		cin >> u >> v;

		G[u].push_back(v);

		G[v].push_back(u);

	}

	  //指定根节点。

	p[root] = 0;   //设定根节点的父亲节点为-1，代表根节点没有父亲节点。

	dfs(root, 0);

	for(int i = 1; i <= n; ++i) {

		cout << p[i] <<" ";

	}

	return 0;

}