`

【并查集】hdu 1325 Is It A Tree? 或 poj 1308 Is It A Tree?

阅读更多

 

/* 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;
}
 
0
0
分享到:
评论

相关推荐

    【包教包会】用树的定义去判断树!(HDU1272)(HDU1325)(POJ1308)

    在计算机科学中,树是一种非常基础且重要的数据...通过编程实现这些条件的检查,可以解决如HDU1272、HDU1325和POJ1308这类题目。掌握这些基本概念和技巧,不仅有助于解决这类问题,也是深入学习图论和数据结构的基础。

    hdu 3333 turing tree 解题报告

    题目“HDU 3333 Turing Tree”要求解决的问题是:给定一个整数序列和一系列区间,计算每个区间内不重复数字的和。由于数据规模较大(N ,000, K ,000),直接的暴力方法效率过低,因此我们需要采用一种更高效的数据...

    (HDUACM201403版_06)并查集(最小生成树)

    杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)

    (HDUACM2010版_06)并查集(最小生成树)

    (HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树

    并查集问题

    1. poj2524.cpp:这是一个POJ(Problem Setter's Online Judge)的编程题目,通常涉及到特定的算法问题,可能需要利用并查集解决连通性或路径查找问题。 2. hdoj1233最小生成树,克鲁斯卡尔.cpp:最小生成树是图论...

    hdu oj poj 题目代码与详解

    【题目代码与详解】是针对在线编程竞赛平台HDU(杭州电子科技大学在线评测系统)和POJ(普林斯顿大学在线判题系统)中的经典题目所编写的解决方案和解析的集合。这些平台是程序员和计算机科学学生提升算法技能、熟悉...

    HDU ZOJ POJ 杭电浙大北大 3大OJAC代码4000份大合集

    利用vjudge源码改造爬虫抓取vjudge全局共享答案资源。 ACMer,请用于参考思路,对拍代码,不要直接提交。

    POJ、HDU、ZOJ、SOJ水题过滤器

    标题中的“POJ、HDU、ZOJ、SOJ水题过滤器”指的是一个工具,它主要用于帮助在ACM(国际大学生程序设计竞赛)训练中筛选出这些在线判题系统中的简单题目,即所谓的“水题”。这些在线判题平台是编程爱好者和参赛者们...

    jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c

    描述中提到的"三道几何题:hdu 1007、hdu 2289、poj 3714"暗示了这是一个关于几何算法的题目集,涉及到三个不同的在线判题系统:HDU(杭州电子科技大学在线评测系统)的1007题和2289题,以及POJ的3714题。...

    HDU&&POJ图论题集

    图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个...

    hdu.rar_hdu

    压缩包内的文件名“朝花夕拾——hdu”可能表示这是一系列关于HDU题目的代码记录,"朝花夕拾"是一个成语,意味着回忆过去的事情,这里可能是暗示这些代码是作者在过去解决HDU题目时留下的,现在整理出来分享或复习。...

    算法竞赛专题解析--并查集1

    【并查集详解】 并查集(Disjoint Set)是一种数据结构,用于高效处理不相交集合的合并和查询操作。在算法竞赛中,它常用于解决如连通子图、最小生成树(如Kruskal算法)以及最近公共祖先(LCA)等问题。其核心思想...

    acm课件 HDU 算法大全

    acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 ...并查集

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU 3038 How Many Answers Are Wrong 带权并查集

    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 ...

    hdu oj 分类(杭州电子科技)

    杭州电子科技大学OJ分类,很适合刚入门的新手哦,分类很详细,是不可多得的资料

    HDU1019(2028)解题报告

    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...

Global site tag (gtag.js) - Google Analytics