nyoj 20水

#include<stdio.h>

#include<string.h>

#define N 110000

struct node {

int u,v,next;

}bian[N*2];

int head[N],yong,pre[N];

void addedge(int u,int v) {

bian[yong].u=u;

bian[yong].v=v;

bian[yong].next=head[u];

head[u]=yong++;

}

int visit[N];

void dfs(int u) {

    visit[u]=1;

    int i;

    for(i=head[u];i!=-1;i=bian[i].next) {

        int v=bian[i].v;

        if(!visit[v]) {

            dfs(v);

          pre[v]=u;

        }

    }

    return ;

}

int main() {

     int t,n,s,i,j,k;

     scanf("%d",&t);

     while(t--) {

        scanf("%d%d",&n,&s);

        memset(head,-1,sizeof(head));

        yong=0;

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

            scanf("%d%d",&j,&k);

            addedge(j,k);

            addedge(k,j);

        }

        pre[s]=-1;

        memset(visit,0,sizeof(visit));

        dfs(s);

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

            printf("%d ",pre[i]);

        printf("%d\n",pre[n]);

     }

return 0;

}
巴特西

nyoj 20水

最新文章

热门文章
