/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2012 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=1325
Name : 1325 Is It A Tree?
Date : Tuesday, April 10, 2012
Time Stage : one hour
Result:
5744703 2012-04-10 16:19:24 Accepted 1325
0MS 612K 1133 B
C++ pyy
Test Data :
Review :
hdu 的数据比poj弱,没有以下两种情况:
0 0
1 1 0 0
答案都是 not a tree。
除此之外要注意的是循环的情况:
1 2 1 3 2 1 0 0 // not a tree
和两棵树的情况:
1 2 3 4 0 0 //not a tree
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std ;
#define MAXN (1002)
int set[MAXN];
int flag;
int tcase;
void init()
{
int i;
memset(set, -1, sizeof(set));
flag = 0;
}
int find(int x)
{
if (set[x] == -1)
set[x] = x;
if (set[x] == x)
return x;
return set[x] = find(set[x]);
}
int main()
{
int i, j;
int x, y;
tcase = 1;
init();
while (scanf("%d %d", &x, &y) != EOF)
{
if (x == -1 && y == -1)
break;
if (x == 0 && y == 0)
{
printf ("Case %d", tcase++);
if (!flag)
{
j = 0;
for (i = 0; i < MAXN; ++i)
if (set[i] == i)
++j;
if (j > 1) // not a tree: 1 2 3 4 0 0, a tree: 0 0
flag = 1;
}
if (!flag)
{
printf (" is a tree.\n");
}
else
printf (" is not a tree.\n");
init();
continue;
}
int px = find(x);
int py = find(y);
if (py != y && px != py || x == y || (x != y && px == py))// not a tree: 1 2 1 3 2 1 0 0
{// not a tree: 1 1 0 0
flag = 1;
}
else
set[py] = set[px];
}
return 0;
}
分享到:
相关推荐
在计算机科学中,树是一种非常基础且重要的数据...通过编程实现这些条件的检查,可以解决如HDU1272、HDU1325和POJ1308这类题目。掌握这些基本概念和技巧,不仅有助于解决这类问题,也是深入学习图论和数据结构的基础。
题目“HDU 3333 Turing Tree”要求解决的问题是:给定一个整数序列和一系列区间,计算每个区间内不重复数字的和。由于数据规模较大(N ,000, K ,000),直接的暴力方法效率过低,因此我们需要采用一种更高效的数据...
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
1. poj2524.cpp:这是一个POJ(Problem Setter's Online Judge)的编程题目,通常涉及到特定的算法问题,可能需要利用并查集解决连通性或路径查找问题。 2. hdoj1233最小生成树,克鲁斯卡尔.cpp:最小生成树是图论...
【题目代码与详解】是针对在线编程竞赛平台HDU(杭州电子科技大学在线评测系统)和POJ(普林斯顿大学在线判题系统)中的经典题目所编写的解决方案和解析的集合。这些平台是程序员和计算机科学学生提升算法技能、熟悉...
利用vjudge源码改造爬虫抓取vjudge全局共享答案资源。 ACMer,请用于参考思路,对拍代码,不要直接提交。
标题中的“POJ、HDU、ZOJ、SOJ水题过滤器”指的是一个工具,它主要用于帮助在ACM(国际大学生程序设计竞赛)训练中筛选出这些在线判题系统中的简单题目,即所谓的“水题”。这些在线判题平台是编程爱好者和参赛者们...
描述中提到的"三道几何题:hdu 1007、hdu 2289、poj 3714"暗示了这是一个关于几何算法的题目集,涉及到三个不同的在线判题系统:HDU(杭州电子科技大学在线评测系统)的1007题和2289题,以及POJ的3714题。...
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个...
压缩包内的文件名“朝花夕拾——hdu”可能表示这是一系列关于HDU题目的代码记录,"朝花夕拾"是一个成语,意味着回忆过去的事情,这里可能是暗示这些代码是作者在过去解决HDU题目时留下的,现在整理出来分享或复习。...
【并查集详解】 并查集(Disjoint Set)是一种数据结构,用于高效处理不相交集合的合并和查询操作。在算法竞赛中,它常用于解决如连通子图、最小生成树(如Kruskal算法)以及最近公共祖先(LCA)等问题。其核心思想...
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 ...并查集
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
FF is a bad boy, he is always wooing TT to play the following game with him. This is a very humdrum game. To begin with, TT should write down a sequence of integers-_-!!(bored). Then, FF can choose a ...
杭州电子科技大学OJ分类,很适合刚入门的新手哦,分类很详细,是不可多得的资料
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. Input Input...