Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- #include <queue>
- using namespace std;
- const int MAXN = 505;
- int N, conn [MAXN][2], how [MAXN][MAXN];
- bool vis [MAXN][MAXN];
- void bfs ()
- {
- queue <pair <int, int> > q;
- q.push (make_pair (0, 0));
- vis [0][0] = true;
- while (!q.empty ())
- {
- pair <int, int> top = q.front (); q.pop ();
- for (int i = 0; i < 2; i++)
- for (int a = 0; a < N; a++)
- if (conn [a][i] == top.first)
- for (int b = 0; b < N; b++)
- if (conn [b][i] == top.second && !vis [a][b])
- {
- vis [a][b] = true;
- how [a][b] = i;
- q.push (make_pair (a, b));
- }
- }
- }
- int main (void)
- {
- scanf ("%d", &N);
- for (int i = 0; i < N; i++)
- for (int j = 0; j < 2; j++)
- {
- scanf ("%d", &conn [i][j]);
- conn [i][j]--;
- }
- bfs ();
- vector <int> st;
- for (int i = 0; i < N; i++)
- st.push_back (i);
- while (st.size () > 1)
- {
- pair <int, int> p (st [0], st [1]);
- while (p != make_pair (0, 0))
- {
- int h = how [p.first][p.second];
- putchar ('A' + h);
- for (int i = 0; i < (int) st.size (); i++)
- st [i] = conn [st [i]][h];
- p = make_pair (conn [p.first][h], conn [p.second][h]);
- }
- sort (st.begin (), st.end ());
- st.resize (unique (st.begin (), st.end ()) - st.begin ());
- }
- putchar ('\n');
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement