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