Advertisement
Guest User

Untitled

a guest
May 24th, 2015
215
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <vector>
  6. #include <string>
  7. #include <cmath>
  8. #include <algorithm>
  9. #include <set>
  10. #include <map>
  11. #include <ctime>
  12. using namespace std;
  13.  
  14. #ifdef LOCAL
  15.     #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  16. #else
  17.     #define eprintf(...) 42
  18. #endif
  19.  
  20. const int N = 110;
  21.  
  22. struct State
  23. {
  24.     int a, b, shift;
  25.     State () : a(), b(), shift() {}
  26.     State (int _a, int _b, int _shift) : a(_a), b(_b), shift(_shift) {}
  27. };
  28.  
  29. int roomCnt[N];
  30. int roomTo[N][N];
  31. int roomPos[N][N];
  32. bool used[N][N][N];
  33. State q[N * N * N];
  34. int n;
  35.  
  36. int getUsed(int a, int b, int sh)
  37. {
  38.     sh += 1;
  39.     return used[a][b][sh];
  40. }
  41.  
  42. void setUsed(int a, int b, int sh, bool value)
  43. {
  44.     sh += 1;
  45.     used[a][b][sh] = value;
  46. }
  47.  
  48. void bfs()
  49. {
  50.     int topQ = 0;
  51.     for (int i = 0; i < n; i++)
  52.         for (int s = 0; s < n; s++)
  53.         {
  54.             if (roomCnt[i] != roomCnt[s])
  55.             {
  56.                 q[topQ++] = State(i, s, -1);
  57.                 setUsed(i, s, -1, true);
  58.             }
  59.         }
  60.  
  61.     for (int i = 0; i < topQ; i++)
  62.     {
  63.         State cur = q[i];
  64.         int a = cur.a;
  65.         int b = cur.b;
  66.         if (cur.shift == -1)
  67.         {
  68.             for (int fst = 0; fst < roomCnt[a]; fst++)
  69.                 for (int scnd = 0; scnd < roomCnt[b]; scnd++)
  70.                 {
  71.                     int toA = roomTo[a][fst];
  72.                     int toB = roomTo[b][scnd];
  73.                     if (roomCnt[toA] != roomCnt[toB]) continue;
  74.                     int shift = roomPos[toB][b] - roomPos[toA][a];
  75.                     if (shift < 0)
  76.                         shift += roomCnt[toA];
  77.                     if (!getUsed(toA, toB, shift))
  78.                     {
  79.                         q[topQ++] = State(toA, toB, shift);
  80.                         setUsed(toA, toB, shift, true);
  81.                     }
  82.                 }
  83.         }
  84.         else
  85.         {
  86.             for (int fst = 0; fst < roomCnt[a]; fst++)
  87.             {
  88.                 int scnd = (fst + cur.shift) % roomCnt[a];
  89.                 int toA = roomTo[a][fst];
  90.                 int toB = roomTo[b][scnd];
  91.                 if (roomCnt[toA] != roomCnt[toB]) continue;
  92.                 int shift = roomPos[toB][b] - roomPos[toA][a];
  93.                 if (shift < 0)
  94.                     shift += roomCnt[toA];
  95.                 if (!getUsed(toA, toB, shift))
  96.                 {
  97.                     q[topQ++] = State(toA, toB, shift);
  98.                     setUsed(toA, toB, shift, true);
  99.                 }
  100.             }
  101.         }
  102.     }
  103. }
  104.  
  105.  
  106. vector <int> cur;
  107. bool usedEq[N];
  108. bool eq[N][N];
  109. void getComp(int v)
  110. {
  111.     cur.push_back(v);
  112.     usedEq[v] = 1;
  113.     for (int i = 0; i < n; i++)
  114.     {
  115.         if (eq[v][i] && !usedEq[i])
  116.             getComp(i);
  117.     }
  118. }
  119.  
  120. vector <int> comps[N];
  121. int cntC = 0;
  122.  
  123. void calcComp()
  124. {
  125.     for (int i = 0; i < n; i++)
  126.     {
  127.         if (usedEq[i]) continue;
  128.         cur.clear();
  129.         getComp(i);
  130.         if (cur.size() > 1)
  131.         {
  132.             sort(cur.begin(), cur.end());
  133.             comps[cntC++] = cur;
  134.         }
  135.     }
  136.     sort(comps, comps + cntC);
  137. }
  138.  
  139. int main()
  140. {
  141.     scanf("%d", &n);
  142.     for (int i = 0; i < n; i++)
  143.     {
  144.         scanf("%d", &roomCnt[i]);
  145.         for (int s = 0; s < roomCnt[i]; s++)
  146.         {
  147.             scanf("%d", &roomTo[i][s]);
  148.             roomTo[i][s]--;
  149.             roomPos[i][roomTo[i][s]] = s;
  150.         }
  151.     }
  152.    
  153.     bfs();
  154.     for (int i = 0; i < n; i++)
  155.         for (int s = 0; s < n; s++)
  156.         {
  157.             if (roomCnt[i] != roomCnt[s]) continue;
  158.             for (int sh = 0; sh < roomCnt[i]; sh++)
  159.                 if (!getUsed(i, s, sh))
  160.                     eq[i][s] = 1;
  161.         }
  162.     calcComp();
  163.     if (cntC == 0)
  164.         puts("none");
  165.     else
  166.     {
  167.         for (int i = 0; i < cntC; i++, puts(""))
  168.             for (int x : comps[i])
  169.                 printf("%d ", x + 1);
  170.     }
  171.  
  172.     return 0;
  173. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement