#include<bits/stdc++.h> using namespace std; int n, m, k, a, it, koniec, PI[1003]; vector<int> v[1003], s[2], W; vector<int>::iterator iT; bool spr(){ for( int i = 0; i<=m; i++ ) PI[i] = 0; int k = 0; for( int q = 2; q<=m; q++ ){ while( k>0 && W[k+1]!=W[q]) k = PI[k]; if( W[k+1]==W[q] ) k++; PI[q] = k; } int q = 0; for( int i = 1; i<s[0].size(); i++ ){ while( q>0 && W[q+1]!=s[0][i] ) q = PI[q]; if( W[q+1]==s[0][i] ) q++; if( q==m ){ return true; } } for( int i = 1; i<s[1].size(); i++ ){ while( q>0 && W[q+1]!=s[1][i] ) q = PI[q]; if( W[q+1]==s[1][i] ) q++; if( q==m ){ return true; } } return false; } int main() { scanf("%d%d", &n, &m); for( int i = 1; i<=n; i++ ){ scanf("%d", &k); while( k-- ){ scanf("%d", &a); v[i].push_back(a); } } W.push_back(0); for( int i = 1; i<=m; i++ ){ scanf("%d", &a); W.push_back(a); } s[0].push_back(1); bool rl = false; for( int i = 1; i<=10004; i++ ){ if( spr() ){ printf("%d\n", i); return 0; } if( !rl ){ for( int j = 0; j<s[0].size(); j++ ) for( int l = 0; l<v[s[0][j]].size(); l++ ) s[1].push_back(v[s[0][j]][l]); rl = true; s[0].clear(); s[0].push_back(0); } else{ for( int j = 0; j<s[1].size(); j++ ) for( int l = 0; l<v[s[1][j]].size(); l++ ) s[0].push_back(v[s[1][j]][l]); rl = false; s[1].clear(); s[1].push_back(0); } } printf("-1\n"); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | #include<bits/stdc++.h> using namespace std; int n, m, k, a, it, koniec, PI[1003]; vector<int> v[1003], s[2], W; vector<int>::iterator iT; bool spr(){ for( int i = 0; i<=m; i++ ) PI[i] = 0; int k = 0; for( int q = 2; q<=m; q++ ){ while( k>0 && W[k+1]!=W[q]) k = PI[k]; if( W[k+1]==W[q] ) k++; PI[q] = k; } int q = 0; for( int i = 1; i<s[0].size(); i++ ){ while( q>0 && W[q+1]!=s[0][i] ) q = PI[q]; if( W[q+1]==s[0][i] ) q++; if( q==m ){ return true; } } for( int i = 1; i<s[1].size(); i++ ){ while( q>0 && W[q+1]!=s[1][i] ) q = PI[q]; if( W[q+1]==s[1][i] ) q++; if( q==m ){ return true; } } return false; } int main() { scanf("%d%d", &n, &m); for( int i = 1; i<=n; i++ ){ scanf("%d", &k); while( k-- ){ scanf("%d", &a); v[i].push_back(a); } } W.push_back(0); for( int i = 1; i<=m; i++ ){ scanf("%d", &a); W.push_back(a); } s[0].push_back(1); bool rl = false; for( int i = 1; i<=10004; i++ ){ if( spr() ){ printf("%d\n", i); return 0; } if( !rl ){ for( int j = 0; j<s[0].size(); j++ ) for( int l = 0; l<v[s[0][j]].size(); l++ ) s[1].push_back(v[s[0][j]][l]); rl = true; s[0].clear(); s[0].push_back(0); } else{ for( int j = 0; j<s[1].size(); j++ ) for( int l = 0; l<v[s[1][j]].size(); l++ ) s[0].push_back(v[s[1][j]][l]); rl = false; s[1].clear(); s[1].push_back(0); } } printf("-1\n"); return 0; } |