推荐一波大佬讲解dfs序和欧拉序非常详细https://www.cnblogs.com/stxy-ferryman/p/7741970.html
题目
传送门
Input 3 2 1 2 -1 0 2 2 0 Output Yes No
题意：给出两个数n，m，下面是n个人的好朋友，如果为-1的话表示他没有好朋友，他的好朋友去了他一定去，这个人去了的话他的好朋友不一定去.下面是m个询问，问x去了y会去吗？
思路：我们只要判断y是否为x的祖先即可，在dfs序中我们以没有好朋友的人分别为根建树然后判断x是否为y的子树即可
AC code
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std
;
vector
<int> g
[100010];
int dfs_
[200020],len
,time
,s
[200020],e
[200020],pos
[200020],vis
[200020];
void dfs(int u
,int fa
)
{
int x
=len
+1;
s
[++len
]=++time
;
dfs_
[len
]=u
;
pos
[u
]=len
;
int sz
=g
[u
].size();
for(int i
=0;i
<sz
;i
++)
{
if(g
[u
][i
]!=fa
)
{
dfs(g
[u
][i
],u
);
}
}
e
[x
]=time
;
}
int main()
{
memset(vis
,0,sizeof(vis
));
int n
,m
;
scanf("%d %d",&n
,&m
);
for(int i
=0;i
<n
;i
++)
{
int to
;
scanf("%d",&to
);
if(to
!=-1)
{
vis
[i
]++;
g
[i
].push_back(to
);
g
[to
].push_back(i
);}
}
for(int i
=0;i
<n
;i
++)
if(!vis
[i
])dfs(i
,-1);
for(int i
=1;i
<=m
;i
++)
{
int x
,y
;
scanf("%d%d",&x
,&y
);
x
=pos
[x
];
y
=pos
[y
];
if(s
[x
]>=s
[y
]&&e
[y
]>=e
[x
])
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}
