无根树转有根树-白红宇

无根树转有根树

阅读量：6309 次

发布时间：2019-06-22

本文共 1546 字，大约阅读时间需要 5 分钟。

问题：输入一个结点的无根树的各条边，并指定一个根结点，要求把该树转化为有根树

测试oj：nyoj

当结点数很多时若用邻接矩阵存储图将占用很大的空间，此时可使用vector或邻接表存储，由于vector内存的增长方式问题也可能会引起内存过大问题，此时邻接表存储更具优势

代码：

使用vector存储：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N = 100005;int p[N];vector
         
           g[N];void build(int u, int fa){    int n = g[u].size();    for(int i=0; i
          
           = 1) printf("%d", p[1]); for(int i=2; i<=n; i++) printf(" %d", p[i]); printf("\n"); } return 0;}

使用邻接链表存储：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         using namespace std;#define N 100005int n;int p[N];int head[N];int len;struct Node {    int data;    int next;}c[2*N];//对于不指明父子关系的结点（无向图）需要2倍的空间void insert(int a, int b){    c[++len].data = b;    c[len].next = head[a];    head[a] = len;}void build(int u, int fa){    for(int i=head[u]; i; i=c[i].next) {        int v = c[i].data;        if(v == fa) continue;        p[v] = u;        build(v, u);    }}void print(){    if(n>=1)        printf("%d", p[1]);    for(int i=2; i<=n; i++)        printf(" %d", p[i]);    printf("\n");}void init(){    len = 0;    memset(head, 0, sizeof(head));    memset(c, 0, sizeof(c));    memset(p, 0, sizeof(p));}int main(){    int t, start;    scanf("%d", &t);    while(t--) {        scanf("%d%d", &n, &start);        init();        int a, b;        for(int i=1; i