codeforces Gym 100187J J. Deck Shuffling dfs

题目链接:

http://codeforces.com/gym/100187/problem/J

题意:

给你一堆牌，和一些洗牌机，可以改变牌的顺序，问你能不能通过洗牌机把数字为x的牌洗到第一个位置。
样例一：最初的牌 4 3 2 1 通过第一个洗牌机把第四个位置的x(=1)洗到第三个位置然后第二个洗牌机把当前在第三个位置x洗到第一个位置

题解:

建边，把洗牌机每个位置–>下一个位置（也就是这个位置的值）
跑一发dfs就好了，其实就问你第一个位置和x所在的位置是否联通

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 2e5+10;
17 
18 int a[maxn],vis[maxn];
19 map<pair<int,int>, int> mp;
20 vector<int> e[maxn];
21 bool f;
22 
23 void dfs(int x){
24     if(x == 1){
25         f = true;
26         return ;
27     }
28     if(f) return ;
29     if(vis[x]) return ;
30 
31     vis[x] = 1;
32 
33     for(int i=0; i<(int)e[x].size(); i++){
34         if(vis[e[x][i]])
35             continue;
36         dfs(e[x][i]);
37     }
38 }
39 
40 int main(){
41     int n = read();
42     for(int i=1; i<=n; i++){
43         int x = read();
44         a[x] = i;
45     }
46 
47     int k = read();
48     for(int i=0; i<k; i++){
49         for(int j=1; j<=n; j++){
50             int x = read();
51             // if(mp[MP(j,x)]!=1){
52             //  mp[MP(j,x)] = 1;
53             //  e[j].PB(x);
54             // }
55             e[j].PB(x);  
56         }
57     }
58 
59     int x = read();
60     dfs(a[x]);
61 
62     if(f) puts("YES");
63     else puts("NO");
64 
65     return 0;
66 }