再谈树---无根树转有根树( dfs搜索转化+fa数组记录父节点) *【模板】

浏览数：24 / 时间：2015年06月08日

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#define N 100000+2
using namespace std;

//无根树转有根树算法
/*
  算法分析：所谓无根树，就是根节点任意的树。我们可以给它确定一个根节点。
  我们可以假定认为某一个节点为根节点，然后从该节点开始进行dfs或者bfs搜索，
  在搜索的过程中，就像记录路径那样记录一个father[]数组，用来记录当前节点的
  父亲节点。算法很简单，需要注意两个地方：
  （*1.设置根节点father[root]=-1; 表示根节点没有父节点
  （*2.bfs或dfs的搜索过程中，判断遇到的点是不是根节点，不是的话就进行父节点的
  指定。如果是根节点的话，千万不要修改，如果忘记判断这个条件，将引起无限递归（dfs）
  或者无限循环（bfs）
*/
int n; //n个节点，n-1条边，vector创建二维数组存储（动态存储可以不用考虑存储大小）
vector<int>q[N];
int fa[N]; //记录父节点信息

void dfs(int u, int father)//递归转化以u为根节点，u的父节点为father
{
    int len=q[u].size(); //遍历与该点相连的点
    for(int i=0; i<len; i++)
    {
        int v=q[u][i]; //获取该点
        if(v!=father) //*判断v和其父节点是否相同，否则引起无限循环
            dfs(v, fa[v]=u); //把v的父节点设为u，然后递归转化以v根节点的子树
    }
}

int main()
{
    scanf("%d", &n);
    int u, v;
    for(int i=0; i<n-1; i++)
    {
        scanf("%d %d", &u, &v);
        q[u].push_back(v);
        q[v].push_back(u);
    }
    //进行dfs转化有根树
    fa[1]=-1;
    dfs(1, -1);

    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。