题目大意:
输入一个数t,表示测试组数。然后每组第一行两个数字n,m,n表示有n只昆虫, 编号从1—n,m表示下面要输入m行交配情况,每行两个整数,表示这两个编号的昆虫为异性,要交配。 要求统计交配过程中是否出现冲突,即是否有两个同性的昆虫发生交配。
[输入输出]: [样例]:
Sample Input
2 (二次测试)
3 3(三条虫子,三对信息)
1 2
2 3
1 3
4 2(四条虫子,二对信息)
1 2
3 4
Sample Output
Scenario #1:
Suspicious bugs found!
Scenario #2:
No suspicious bugs found!
分析:
一道并查集的练习题。将所有虫子分到两个集合中,公的一个集合,母的一个集合,读入一对信息时,判断它们是不是属于同一集合,是则发生同性恋.
import java.util.Scanner;
public class Main{
private int n;
private int m;
private int father[];
private int other[]; //other[x]表示x的另一半是谁
private int x[];
private int y[];
private boolean mark;
public Main(int n,int m,int[] x,int[] y){
this.n=n;
this.m=m;
this.x=x;
this.y=y;
father=new int[n+1];
other=new int[n+1];
for(int i=0;i<n+1;i++){
father[i]=i;
other[i]=0;
}
mark=false;
}
private int Find_Set(int x){
int k,root;
root=x;
while(root!=father[root]) //循环找x的根
root=father[root];
while(x!=root)//本循环修改查找路径中的所有节点使其指向根节点---压缩
{
k=father[x];
father[x]=root;//指向根节点
x=k;
}
return x;
}
private void Union(int x,int y){
int fx=Find_Set(x);
int fy=Find_Set(y);
father[fx]=fy;
}
public void go(int d){
int fx,fy,xl,yl;
for(int l=1;l<=m;l++){
xl=x[l];
yl=y[l];
if(!mark){
fx=Find_Set(xl);
fy=Find_Set(yl);
if(fx==fy){//出现同性恋
mark=true;
break;
}else{//没出现同性恋,合并。公的在一个集合,母的在另一个集合
if(other[xl]!=0){
Union(other[xl],yl);
} else if(other[yl]!=0){
Union(other[yl],xl);
} else {
other[xl]=yl;
other[yl]=xl;
}
}
}
}
System.out.println("Scenario #"+d+":");
if(mark)
System.out.println("Suspicious bugs found!");
else
System.out.println("No suspicious bugs found!");
System.out.println();
}
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int t,n,m;
int[] x;
int[] y;
t=in.nextInt();
for(int d=1;d<=t;d++){
n=in.nextInt();
m=in.nextInt();
x=new int[m+1];
y=new int[m+1];
for(int l=1;l<=m;l++){
x[l]=in.nextInt();
y[l]=in.nextInt();
}
Main ma=new Main(n,m,x,y);
ma.go(d);
}
}
}
代码是AC了(POJ2492),差一点超时,以上代码是10976954_AC_9516MS_15372K.java,
大家有兴趣的,帮分析分析吧!
分享到:
相关推荐
昆虫动物识别
1、YOLO昆虫检测数据集,1000多张使用lableimg标注软件,标注好的真实场景的高质量图片数据,图片格式为jpg,标签有两种,分别为VOC格式和yolo格式,分别保存在两个文件夹中,可以直接用于YOLO系列的昆虫目标检测;...
数据集介绍 提供了217张图片, 包含6种昆虫,分别是acuminatus armandi boerner coleoptera leconte linnaeus。 包含了图片和标注。训练集:验证集:测试集=7:2:1
每年在昆虫学或实验室中产生数千亿只昆虫。 这些昆虫被饲养起来作为害虫防治计划的饲料,用于生产各种产品(例如纺织品和食品),用于研究和教育以及许多目的。 在此提出了一个概念,即期望饲养条件能够模拟衍生目标...
昆虫繁殖问题
昆虫是地球上数量最多的生物,约占所有动物物种的66%,是几乎所有类型的有机物的良好分散者和剥削者,几乎在任何地方都可以发现,构成了每个生态系统的重要组成部分,并且至关重要在我们的食品供应链中提供有价值...
广州市小学科学教师昆虫分类知识竞赛试题广州市小学科学教师昆虫分类知识竞赛试题广州市小学科学教师昆虫分类知识竞赛试题广州市小学科学教师昆虫分类知识竞赛试题广州市小学科学教师昆虫分类知识竞赛试题广州市小学...
欧美昆虫网站模板 昆虫模板 欧美模板 html模板 动物模板
昆虫生态及预测预报复习资料.pdf
基于机器视觉实现昆虫识别计数系统python源码+数据集+模型+详细项目说明.zip 【项目任务】 图片中昆虫虫体计数 PyQt和OpenCV结合做出基本界面 摄像头Frame中检测虫体数目,并在界面中显示标出 学习昆虫图像特征的...
森林昆虫学实习报告.doc
实验十一昆虫的采集及分类昆虫标本的制作学习教案.pptx
利用代码实现的利用键盘来控制昆虫赛跑的小游戏
山东农业大学-园艺昆虫学-复习题库含答案
千千静音的各种皮肤 千千静音的各种皮肤机器昆虫
1312:【例3.4】昆虫繁殖 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 12342 通过数: 6070 【题目描述】 科学家在热带森林中发现了一种特殊的昆虫,这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵,每对卵要过...
半翅目昆虫的基因组大小,宋凡,王建赟,基因组大小可以用多种方法较为准确地估计出来,目前约有830种昆虫的基因组大小得到测定,大多测自全变态昆虫。已知昆虫的基因组大
昆虫博客CSS网页模板 绿色 商务 网页 模板 植物 昆虫 大自然 商业 公司 设计 主页 HTML DIV+CSS 模板下载
《昆虫记》必考知识点最全整理(含习题及答案).pdf
最新2022苏教版科学四年级下册《探究昆虫的奥秘》精美教案 .pdf