Deck Shuffling
题目链接
分类：dfs
1.题意概述
给你一堆牌，和一些洗牌机，可以改变牌的顺序，问你能不能通过洗牌机把数字为x的牌洗到第一个位置。
Sample：最初的牌 4 3 2 1 通过第一个洗牌机把第四个位置的x(pos=1)洗到第三个位置，然后第二个洗牌机把当前在第三个位置x洗到第一个位置
2.解题思路
判断连通问题，建边以后既可以跑一发DFS判断也可以直接顺着边去模拟，最后看是否访问1即可。
3.AC代码
int cnt, E[maxn], head[maxn], to[maxn];
int n, k, a[maxn], d[maxn], wide, x;
bool vis[maxn];
void addedge(
int u,
int v) {
E[++cnt] = head[u];
head[u] = cnt;
to[cnt] = v;
}
int main() {
scanf(
"%d", &n);
rep(i,
1, n +
1)
scanf(
"%d", &a[i]);
scanf(
"%d", &k);
rep (i,
0, k) {
rep(j,
1, n +
1) {
int v;
scanf(
"%d", &v);
addedge(v, j);
}
}
scanf(
"%d", &x);
rep(i,
1, n +
1) {
if (a[i] == x) {
x = i;
break;
}
}
d[
0] = x; wide =
1; vis[x] =
1;
rep(i,
0, wide) {
int j = head[d[i]];
while (j) {
if (!vis[to[j]]) {
d[wide++] = to[j];
vis[to[j]] =
1;
}
j = E[j];
}
}
puts(vis[
1] ?
"YES" :
"NO");
return 0;
}
