1-n, a total of n numbers, initially each number is counted as a string independently, and then n-1 merges will be carried out, each merge operation, will put one string behind another string.
When merging, two numbers, x y, are given, indicating that the string beginning with y is placed behind the string beginning with X. For example:
13 (3 after 1, => (13), 2, 4)
24 (4 after 2, => (13), (24))
12 (2 after 1, => (13 24))
After n - 1 merges, all the numbers of the last remaining string are output sequentially.
input
Line 1: 1 number n (2 <= n <= 10000)
In the latter n - 1 line, there are two numbers x y in each line, corresponding to N - 1 merge operation. The string beginning with y is placed at the end of the string beginning with X.
output
The output consists of n rows, one number per row, corresponding to the N numbers contained in the final string.
sample input
4
1 3
2 4
1 2
sample output
1
3
2
4
Explanation:
This problem can't be solved by using the container list in STL. Firstly, n single linked lists are defined. The first element of each list is 1, 2, 3, and __________. N, and then enter n-1 pairs of x,y. The title means to put the list beginning with y after the list beginning with X as a whole, so first traverse to find the single list beginning with y, record the subscript y_index, and then find the single list beginning with x, and put the elements of the single list beginning with y after the list beginning with X. Face, and finally remember to empty the list that starts with y, because this string has been put behind X.
Then the last input x is the only string. Record the subscripts and traverse the output elements once.
Code:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <deque>
#include <list>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <iterator>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double E = exp(1.0);
const int MOD = 1e9+7;
const int MAX = 1e4+5;
int n;
list <int> List[MAX];
int main()
{
/*
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
*/
while(cin >> n)
{
for(int i = 1; i <= n; i++)
{
List[i].push_back(i);
}
// Place the whole string beginning with y behind the whole string beginning with x
// Initial: 1, 2, 3, 4
// 1 3 (1 3),2,4
// 2 4 (1 3),(2 4)
// 1 2 (1 3 2 4)
int x,y;
int last_x;
for(int i = 1; i <= n-1; i++)
{
cin >> x >> y;
int y_index;
for(int j = 1; j <= n; j++)
{
// Find a string that starts with y
if(List[j].front() == y)
{
y_index = j;
}
}
for(int j = 1; j <= n; j++)
{
// Find a string that starts with x
if(List[j].front() == x)
{
// Place the whole string beginning with y behind the whole string beginning with x
// Then delete the y string
for(auto it = List[y_index].begin(); it != List[y_index].end(); it++)
{
List[j].push_back(*it);
}
List[y_index].clear();
}
}
if(i == n-1)
last_x = x;
}
for(auto it = List[last_x].begin(); it != List[last_x].end(); it++)
{
printf("%d\n",*it);
}
}
return 0;
}