描述

输入一个n个节点的无根树的各条边，并指定一个根节点，要求把该树转化为有根树，输出各个节点的父节点编号。

题解

1. 树是一种特殊的图，因此可以使用邻接矩阵来表示。如果使用二维数组来存储邻接矩阵，则需要O(n²)个元素的空间，因此改用vector数组。
2. 从根节点开始对树进行dfs。遍历到每个节点时，使用数组p来存储该节点的父节点。

注意：状态转移时，一定要判断下一个状态（当前状态的儿子）是否和下一个状态的父节点（也就是当前状态）相等，否则会引起无限递归。以上图为例，当执行dfs(5,1)时，由于存储树结构时，节点1亦是5的儿子节点，所以如果不进行判断，则会发生dfs(1,5)，导致循环递归。

	int temp=G[u][i];if(temp!=fa){dfs(temp,p[temp]=u);}

代码

#include 
#include
#include
#define maxn 105
using namespace std;
vector<int> G[maxn];
int p[maxn];
int n;
void read_tree(){int u,v;for(int i=0;i<n-1;i++){scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}
}
void dfs(int u,int fa){int len=G[u].size();for(int i=0;i<len;i++){int temp=G[u][i];if(temp!=fa){dfs(temp,p[temp]=u);}}
}
int main()
{while(scanf("%d",&n)==1){int root=-1;scanf("%d",&root);p[root]=-1;read_tree();dfs(root,-1);for(int i=0;i<n;i++){printf("%d ",p[i]);}}return 0;
}