/* 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;
}
分享到:
相关推荐
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
Hdu 3333解题报告 题意描述: 给你n个数现在要你求在k个区间上[ai, bi]的不相同的数之和各是多少. N,000; k,000; 显然,这题不能用暴力来做。 这题我们选择用线段数来做。
标题这几题都是去判断树的,只是输出不一样 要用定义去做树,那肯定要知道树是什么 学习的时候很迷茫是没搞清楚大方向 什么是大方向呢? 两个字:图论 树肯定是图,但图不一定是树 搞清楚这么几个知识点就可以愉快的...
很多经典的杭电oj与poj习题的ac代码与详解!全部ac,决对没有错误的代码!
利用vjudge源码改造爬虫抓取vjudge全局共享答案资源。 ACMer,请用于参考思路,对拍代码,不要直接提交。
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个...
自动探测POJ、HDU、SOJ、ZOJ水题,对于有志于刷遍各种水题的ACMer来说非常有用
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 ...并查集
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...
杭电ACMhdu1163
acm hdu as easy as a+b
hdu1001解题报告
三道几何题:hdu 1007、hdu 2289、poj 3714
hdu 1574 passed sorce