题目链接:http://codeforces.com/contest/755/problem/C

题意:PolandBall 生活在一个森林模型的环境中,定义森林由若干树组成,定义树为K个点,K-1条无向边的图。现在给定每个家庭在对应的树上离他最远的另一个家庭的编号。问这个森林有多少棵树组成。

思路:由于只给出了每个点在树上离他最远的点的坐标而不知道整体结构,但是可以知道该点和给定离他最远的点一定是在同一颗树上,所以维护一个并查集,最后有多少个连通分量就是有多少棵树了。

import java.io.PrintWriter;
import java.util.*; public class Main {
public static final int MAXN=10000+10;
public static int fa[]=new int [MAXN];
public static int ans;
public static int find(int x){
return x==fa[x] ? (fa[x]) : (fa[x]=find(fa[x]));
}
public static void Union(int x,int y){
int rootx=find(x),rooty=find(y);
if(rootx==rooty)
{
return;
}
fa[rooty]=rootx;
ans--;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out);
int n=cin.nextInt(); ans=n;
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<=n;i++){
Union(i,cin.nextInt());
}
out.println(ans);
cin.close();
out.flush();
}
}

最新文章

  1. Eclipse Android 解决Gen文件夹为空的问题
  2. storm入门(一):storm编程框架与举例
  3. 用python监控Linux,CPU,内存,硬盘
  4. Tomcat Server Configuration Automation Reinforcement
  5. eclipse新建web项目,运行后在tomcat安装目录下webapps中没有该项目
  6. hdu 4000 树状数组
  7. C语言数组和指针的理解_在取地址运算上的操作_指针加减操作_a 和&amp;a 的区别
  8. BaseFragment的定义—所有Fragment的父类
  9. 软件工程个人第二小项目——wc
  10. jsonp其实很简单【ajax跨域请求】
  11. 【bzoj4571&amp;&amp;SCOI2016美味】
  12. SQLServer学习记录
  13. CentOS7配置gradle,或配置maven
  14. python web篇 Django centos 命令版
  15. dojo:如何为表格添加从数据库获得存储的下拉框
  16. Delphi 三层TDataSetProvider
  17. [JSOI 2007]字符加密Cipher
  18. C# winform单元格的formatted值的类型错误 DataGridView中CheckBox列运行时候System.FormatException异常
  19. JS模块化写法(转)
  20. UISegmentedControl的基本用法

热门文章

  1. 前端面试题:不使用loop循环,创建一个长度为100的数组,并且每个元素的值等于它的下标,,怎么实现好?
  2. php长连接和短连接的使用场景
  3. 为什么每次打出的包都是Release版本呢?
  4. Python算法每日一题--002--求众数
  5. Learn Python the hard way, ex39 列表的操作
  6. Unity3D热更新方案网摘总结
  7. 2019牛客暑期多校训练营(第三场)H Magic Line
  8. VS2012不显示最近打开的文件
  9. 工作笔记:phpstrom、docker、phpunit进行单元测试
  10. 20190820 On Java8 第十章 接口