题目：输入一个拥有N个结点的无根树的边，指点一个结点为根节点，把这棵树转化为一棵有根树，输出各个节点的父亲编号。n<=10^6。

　　我使用一个vector数组G[i](i为节点编号)保存各个节点的相邻点，然后使用R[i]（i为节点编号）保存每个节点的父节点的编号。把各个边的信息保存到G[i]之后，从指定节点开始，采用dfs算法遍历，把各个节点的父节点编号存放在R[i],最后输出。

 

　　以下是全部代码：

　　

1 #include 
     
       2 #include 
      
        3  4  5 using namespace std; 6  7 #define MAX 1000001 8  9 vector
       
         G[MAX];10 int P[MAX];11 12 void inputTree(int n)13 {14     int u, v; //存放两个节点编号15     16     //输入边信息17     for (int i = 0; i < n-1; ++i)18     {19         cin >> u >> v;20         G[u].push_back(v);21         G[v].push_back(u);22     }23 }24 25 //u为当前节点,fa为它的父节点26 void dfs(int u, int fa)27 {28     int d = G[u].size();29     30     for (int i = 0; i < d; ++i)31     {32         int v = G[u][i];33         34         if (v != fa)35             dfs(v, P[v] = u);36     }37 }38 39 int main()40 {41     int n; //节点数42     int root; //根节点编号43     cin >> n;44     inputTree(n);45 46     cin >> root;47     P[root] = -1;48     dfs(root, P[root]);49     50     //输出51     for (int i = 0; i < n; ++i)52     {53         cout << "R[" << i << "] : " << P[i] << endl;54     }55     56     return 0;57 }