#include <iostream> #include <vector> #include <queue> #include <algorithm> #include <string> #include <stack> #include <set> #include <list> #include <map> using namespace std; bool containsS(vector < int > State, vector < int > S) { vector < int > Joined; for(int i = 0; i < S.size(); i++) Joined.push_back(S[i]); Joined.push_back(-1); for(int i = 0; i < State.size(); i++) Joined.push_back(State[i]); int n = Joined.size(); vector < int > P(n); int t = 0; P[0] = 0; P[1] = 0; for(int i = 1; i < n; i++) { while (t > 0 && Joined[t] != Joined[i]) t = P[t-1]; if (Joined[t] == Joined[i]) t++; P[i] = t; } for(int i = 0; i < P.size(); i++) if(P[i] == S.size()) return 1; return 0; } int main() { ios_base::sync_with_stdio(0); int n, m; cin >> n >> m; vector < vector < int > > V(n); for(int i = 0; i < n; i++) { int length; cin >> length; for(int j = 0; j < length; j++) { int a; cin >> a; a--; V[i].push_back(a); } } vector < int > S(m); for(int i = 0; i < m; i++) { int a; cin >> a; a--; S[i] = a; } vector < int > State(1, 0); vector < int > Tmp; int cnt = 1; while(!containsS(State, S)) { for(int i = 0; i < State.size(); i++) for(int j = 0; j < V[State[i]].size(); j++) Tmp.push_back(V[State[i]][j]); State = Tmp; Tmp.resize(0); cnt++; if(cnt >= 10) { cout << -1; return 0; } } cout << cnt; 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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 | #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <string> #include <stack> #include <set> #include <list> #include <map> using namespace std; bool containsS(vector < int > State, vector < int > S) { vector < int > Joined; for(int i = 0; i < S.size(); i++) Joined.push_back(S[i]); Joined.push_back(-1); for(int i = 0; i < State.size(); i++) Joined.push_back(State[i]); int n = Joined.size(); vector < int > P(n); int t = 0; P[0] = 0; P[1] = 0; for(int i = 1; i < n; i++) { while (t > 0 && Joined[t] != Joined[i]) t = P[t-1]; if (Joined[t] == Joined[i]) t++; P[i] = t; } for(int i = 0; i < P.size(); i++) if(P[i] == S.size()) return 1; return 0; } int main() { ios_base::sync_with_stdio(0); int n, m; cin >> n >> m; vector < vector < int > > V(n); for(int i = 0; i < n; i++) { int length; cin >> length; for(int j = 0; j < length; j++) { int a; cin >> a; a--; V[i].push_back(a); } } vector < int > S(m); for(int i = 0; i < m; i++) { int a; cin >> a; a--; S[i] = a; } vector < int > State(1, 0); vector < int > Tmp; int cnt = 1; while(!containsS(State, S)) { for(int i = 0; i < State.size(); i++) for(int j = 0; j < V[State[i]].size(); j++) Tmp.push_back(V[State[i]][j]); State = Tmp; Tmp.resize(0); cnt++; if(cnt >= 10) { cout << -1; return 0; } } cout << cnt; return 0; } |