Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <vector>
- #include <string>
- #include <cmath>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <ctime>
- using namespace std;
- #ifdef LOCAL
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #else
- #define eprintf(...) 42
- #endif
- const int N = 110;
- struct State
- {
- int a, b, shift;
- State () : a(), b(), shift() {}
- State (int _a, int _b, int _shift) : a(_a), b(_b), shift(_shift) {}
- };
- int roomCnt[N];
- int roomTo[N][N];
- int roomPos[N][N];
- bool used[N][N][N];
- State q[N * N * N];
- int n;
- int getUsed(int a, int b, int sh)
- {
- sh += 1;
- return used[a][b][sh];
- }
- void setUsed(int a, int b, int sh, bool value)
- {
- sh += 1;
- used[a][b][sh] = value;
- }
- void bfs()
- {
- int topQ = 0;
- for (int i = 0; i < n; i++)
- for (int s = 0; s < n; s++)
- {
- if (roomCnt[i] != roomCnt[s])
- {
- q[topQ++] = State(i, s, -1);
- setUsed(i, s, -1, true);
- }
- }
- for (int i = 0; i < topQ; i++)
- {
- State cur = q[i];
- int a = cur.a;
- int b = cur.b;
- if (cur.shift == -1)
- {
- for (int fst = 0; fst < roomCnt[a]; fst++)
- for (int scnd = 0; scnd < roomCnt[b]; scnd++)
- {
- int toA = roomTo[a][fst];
- int toB = roomTo[b][scnd];
- if (roomCnt[toA] != roomCnt[toB]) continue;
- int shift = roomPos[toB][b] - roomPos[toA][a];
- if (shift < 0)
- shift += roomCnt[toA];
- if (!getUsed(toA, toB, shift))
- {
- q[topQ++] = State(toA, toB, shift);
- setUsed(toA, toB, shift, true);
- }
- }
- }
- else
- {
- for (int fst = 0; fst < roomCnt[a]; fst++)
- {
- int scnd = (fst + cur.shift) % roomCnt[a];
- int toA = roomTo[a][fst];
- int toB = roomTo[b][scnd];
- if (roomCnt[toA] != roomCnt[toB]) continue;
- int shift = roomPos[toB][b] - roomPos[toA][a];
- if (shift < 0)
- shift += roomCnt[toA];
- if (!getUsed(toA, toB, shift))
- {
- q[topQ++] = State(toA, toB, shift);
- setUsed(toA, toB, shift, true);
- }
- }
- }
- }
- }
- vector <int> cur;
- bool usedEq[N];
- bool eq[N][N];
- void getComp(int v)
- {
- cur.push_back(v);
- usedEq[v] = 1;
- for (int i = 0; i < n; i++)
- {
- if (eq[v][i] && !usedEq[i])
- getComp(i);
- }
- }
- vector <int> comps[N];
- int cntC = 0;
- void calcComp()
- {
- for (int i = 0; i < n; i++)
- {
- if (usedEq[i]) continue;
- cur.clear();
- getComp(i);
- if (cur.size() > 1)
- {
- sort(cur.begin(), cur.end());
- comps[cntC++] = cur;
- }
- }
- sort(comps, comps + cntC);
- }
- int main()
- {
- scanf("%d", &n);
- for (int i = 0; i < n; i++)
- {
- scanf("%d", &roomCnt[i]);
- for (int s = 0; s < roomCnt[i]; s++)
- {
- scanf("%d", &roomTo[i][s]);
- roomTo[i][s]--;
- roomPos[i][roomTo[i][s]] = s;
- }
- }
- bfs();
- for (int i = 0; i < n; i++)
- for (int s = 0; s < n; s++)
- {
- if (roomCnt[i] != roomCnt[s]) continue;
- for (int sh = 0; sh < roomCnt[i]; sh++)
- if (!getUsed(i, s, sh))
- eq[i][s] = 1;
- }
- calcComp();
- if (cntC == 0)
- puts("none");
- else
- {
- for (int i = 0; i < cntC; i++, puts(""))
- for (int x : comps[i])
- printf("%d ", x + 1);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement