Problem   Codeforces #541 (Div2) - F. Asya And Kittens

Time Limit: 2000 mSec

Problem Description

Input

The first line contains a single integer nn (2≤n≤150000) — the number of kittens.

Each of the following n−1lines contains integers xi and yi (1≤xi,yi≤n, xi≠yi) — indices of kittens, which got together due to the border removal on the corresponding day.

It's guaranteed, that the kittens xi and yi were in the different cells before this day.

Output

For every cell from 1 to n print a single integer — the index of the kitten from 1 to n, who was originally in it.

All printed integers must be distinct.

It's guaranteed, that there is at least one answer possible. In case there are multiple possible answers, print any of them.

Sample Input

5
1 4
2 5
3 1
4 5

Sample Output

3 1 4 2 5

题解:并查集+链表,始终把y所在的集合加到x所在集合的右边,让每个集合的根始终保持在最左边,维护一下每个集合最左边元素,链表连一连即可,这种题拼的就是手速。

 #include <bits/stdc++.h>

 using namespace std;

 #define REP(i, n) for (int i = 1; i <= (n); i++)
#define sqr(x) ((x) * (x)) const int maxn = + ;
const int maxm = + ;
const int maxs = + ; typedef long long LL;
typedef pair<int, int> pii;
typedef pair<double, double> pdd; const LL unit = 1LL;
const int INF = 0x3f3f3f3f;
const LL mod = ;
const double eps = 1e-;
const double inf = 1e15;
const double pi = acos(-1.0); int n;
int fa[maxn], ri[maxn];
int ans[maxn];
int edge[maxn]; int findn(int x)
{
return x == fa[x] ? x : fa[x] = findn(fa[x]);
} void init()
{
for (int i = ; i < maxn; i++)
{
fa[i] = edge[i] = ri[i] = i;
}
} int main()
{
ios::sync_with_stdio(false);
cin.tie();
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
init();
cin >> n;
int x, y;
for (int i = ; i < n - ; i++)
{
cin >> x >> y;
int fx = findn(x), fy = findn(y);
fa[fy] = fx;
ri[edge[fx]] = fy;
edge[fx] = edge[fy];
}
int root = -;
for (int i = ; i <= n; i++)
{
if (findn(i) == i)
{
root = i;
}
}
ans[] = root;
int cnt = ;
for (int i = ri[root]; cnt++; i = ri[i])
{
ans[cnt] = i;
if (cnt == n)
break;
}
for(int i = ; i <= n; i++)
{
cout << ans[i];
if(i != n)
{
cout << " ";
}
else
{
cout << endl;
} }
return ;
}

最新文章

  1. C# HTTP上传文件
  2. Python 变量类型
  3. MQ安装配置
  4. Oracle数据创建表空间
  5. UML从需求到实现----包图
  6. Codeforces Round #313 (Div. 1) C. Gerald and Giant Chess
  7. px和em之间的转换
  8. FIREDAC TFDCONNECTION连接MYSQL数据库
  9. 机器学习公开课~~~~mooc
  10. android http同步请求
  11. LearnCpp.com
  12. Extjs 树节点操作常用属性
  13. HTML的Tomcat
  14. visual studio 启动无法打开IIS express
  15. 类中的 this关键字
  16. netty 学习(1)
  17. .net core 使用NPOI填充Word模板导出Word
  18. Centos开机自启动脚本的制作
  19. 福大软工 &#183; 第十一次作业 - Alpha 事后诸葛亮(团队)
  20. 20165236 2017-2018-2 《Java程序设计》第八周学习总结

热门文章

  1. [转]simple sample to create and use widget for nopcommerce
  2. WPF学习之路由事件
  3. Nginx+Lua(OpenResty)开发高性能Web应用
  4. qq被冻结怎么激活
  5. C# 与 C++ 数据类型对照
  6. Yii CModel中rules验证规则
  7. Android 使用定时器在指定日期及时间执行任务
  8. FreeMarker 自己定义指令(三)
  9. oracle 高级分组
  10. JavaScript中的字符串
  11. 老李推荐:第8章2节《MonkeyRunner源码剖析》MonkeyRunner启动运行过程-解析处理命令行参数 2
  12. ChartCtrl源码剖析之——CChartObject类
  13. String类的构造方法(2)
  14. iconfont 怎么在项目中使用图标库
  15. ztree树应用
  16. anaconda的安装教程和使用方法
  17. Android逆向基础----Android Dalvik虚拟机
  18. 一句话shell【php】
  19. Flightphp了解一下
  20. pta l2-14(列车调度)