Advertisement
Guest User

Untitled

a guest
May 22nd, 2017
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. const int MAXN = 505;
  7.  
  8. int N, conn [MAXN][2], how [MAXN][MAXN];
  9. bool vis [MAXN][MAXN];
  10.  
  11. void bfs ()
  12. {
  13.     queue <pair <int, int> > q;
  14.     q.push (make_pair (0, 0));
  15.     vis [0][0] = true;
  16.  
  17.     while (!q.empty ())
  18.     {
  19.         pair <int, int> top = q.front (); q.pop ();
  20.  
  21.         for (int i = 0; i < 2; i++)
  22.             for (int a = 0; a < N; a++)
  23.                 if (conn [a][i] == top.first)
  24.                     for (int b = 0; b < N; b++)
  25.                         if (conn [b][i] == top.second && !vis [a][b])
  26.                         {
  27.                             vis [a][b] = true;
  28.                             how [a][b] = i;
  29.                             q.push (make_pair (a, b));
  30.                         }
  31.     }
  32. }
  33.  
  34. int main (void)
  35. {
  36.     scanf ("%d", &N);
  37.  
  38.     for (int i = 0; i < N; i++)
  39.         for (int j = 0; j < 2; j++)
  40.         {
  41.             scanf ("%d", &conn [i][j]);
  42.             conn [i][j]--;
  43.         }
  44.  
  45.     bfs ();
  46.  
  47.     vector <int> st;
  48.  
  49.     for (int i = 0; i < N; i++)
  50.         st.push_back (i);
  51.  
  52.     while (st.size () > 1)
  53.     {
  54.         pair <int, int> p (st [0], st [1]);
  55.  
  56.         while (p != make_pair (0, 0))
  57.         {
  58.             int h = how [p.first][p.second];
  59.             putchar ('A' + h);
  60.  
  61.             for (int i = 0; i < (int) st.size (); i++)
  62.                 st [i] = conn [st [i]][h];
  63.  
  64.             p = make_pair (conn [p.first][h], conn [p.second][h]);
  65.         }
  66.  
  67.         sort (st.begin (), st.end ());
  68.         st.resize (unique (st.begin (), st.end ()) - st.begin ());
  69.     }
  70.  
  71.     putchar ('\n');
  72.  
  73.     return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement