#include<bits/stdc++.h>
const int N=2e6+50;
int n, head[N], nxt[N], ver[N], dep[N],prv[N],suc[N],cnt;
inline void add(int u, int v)
{
nxt[++cnt] =head[u], ver[cnt]=v, head[u]=cnt;
}
void dfs (int u, int fa)
{
dep[u]=dep[fa]+1;
for(int i=head[u]; i; i=nxt[i])
if (ver[i] !=fa) dfs(ver[i],u);
}
void solve(int u,int fa,bool rv=false)
{
int isLeaf=true,t=u;
for (int i=head[u]; i; i=nxt[i])
{
int y=ver[i];
if (y !=fa)
{
isLeaf= false;
solve(y,u,rv ^ 1);
if (rv)
{
int mp=prv[y];
suc[t]=y,prv[y]=t,t=mp;
}
else
{
suc[t]=suc[y];
prv[suc[y]]=t;
suc[t=y]=0;
}
}
}
if (isLeaf) suc[u] =prv[u]=u;
else suc[t]=u,prv[u]=t;
}
int main()
{
scanf ("%d", &n) ;
for (int i=1,u,v; i<n; ++i)
{
scanf ("%d%d",&u,&v);
add(u,v) ; add(v,u) ;
}
dfs (1,1) ; solve(1,-1);
printf("1 ");
int p=1,v=suc[p];
while (v !=p)
{
printf ("%d ",v) ;
v=suc[v];
}
return 0;
}
提示：该程序的输入为一张n个点的连通图。
判断题
1) (1分)由程序的建图方式，可以猜测输入的图G为一棵树。( )
2) 函数dfs(int, int)用于计算每个节点的深度，并存储至数组dep[]。( )
3) 函数solve()通过广度优先搜索，在树T上构造了一条路径。( )
4) (2分)程序将输出一个大小为n的排列。( )
选择题
5) 该程序读入以下数据后，输出结果为( )。8 \1 2 \2 3 \3 4\4 5\4 6\4 7\7 8
6) (5分)该程序对于给定的图G，构造出另一个图G'，并在G'上构造某条特殊的路径。记dg(u,v)为图G中u,v两点的距离，则有关G'(V',E')的构造方法与找出的路径的说法,正确的为( )