1590 合并数字
STL - List 练习题,
直接用 List 模拟题意即可,或者手写链表也行。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
list<int> List[N];
int main(){
int n,x,y,y_idx,x_idx;
cin >> n ;
for(int i = 1;i <= n; ++i){//初始化全为 i
List[i].push_back(i);
}
for(int i = 1;i <= n-1; ++i){ // n-1 次 合并操作
cin >> x >> y;
for(int j = 1;j <= n; ++j){// 找到 y
if(List[j].front() == y){
y_idx = j;
break;
}
}
for(int j = 1;j <= n; ++j){// 找到 x
if(List[j].front() == x){
for(auto it = List[y_idx].begin();it != List[y_idx].end(); ++it){
List[j].push_back(*it);// 把 y 链表上的所有数字放到 x 的末尾
}
List[y_idx].clear();// 清空 y
break;
}
}
x_idx = x;// 最后一次的 x 即最终的链表(每次赋值更新)
}
for(auto it = List[x_idx].begin(); it != List[x_idx].end(); ++it){
cout << *it << endl;
}
return 0;
}