`
king_tt
  • 浏览: 2083689 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

HDU 1272 小希的迷宫 + 1325 Is It A Tree? , 并查集

 
阅读更多

题目链接:

小希的迷宫:http://acm.hdu.edu.cn/showproblem.php?pid=1272

Is It A Tree:http://acm.hdu.edu.cn/showproblem.php?pid=1325


题目类型: 并查集


题目:

A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties.
There is exactly one node, called the root, to which no directed edges point.

Every node except the root has exactly one edge pointing to it.

There is a unique sequence of directed edges from the root to each node.

For example, consider the illustrations below, in which nodes are represented by circles and edges are represented by lines with arrowheads. The first two of these are trees, but the last is not.



In this problem you will be given several descriptions of collections of nodes connected by directed edges. For each of these you are to determine if the collection satisfies the definition of a tree or not.

Input
The input will consist of a sequence of descriptions (test cases) followed by a pair of negative integers. Each test case will consist of a sequence of edge descriptions followed by a pair of zeroes Each edge description will consist of a pair of integers; the first integer identifies the node from which the edge begins, and the second integer identifies the node to which the edge is directed. Node numbers will always be greater than zero.

Output
For each test case display the line ``Case k is a tree." or the line ``Case k is not a tree.", where k corresponds to the test case number (they are sequentially numbered starting with 1).

Sample Input
6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1

Sample Output
Case 1 is a tree. Case 2 is a tree. Case 3 is not a tree.



题目大意:

HDU的小希的迷宫是Is It A Tree?这一题的汉化版。题目翻译可看小希的迷宫。

大概意思是给定一些结点的关系, 然后要判断这些结点是否组成一棵树。


分析与总结:

判断是否是一棵树的几个要点:

(1)判断是否有回路,有回路的就不是树。这个可用并查集来做。一旦给定的两个结点a,b是属于同一个集合的,那么便可判定有回路。


(2)看是否只有一个连通分支, 如果有多个,那么就成了森林。 这个可以用并查集来判断。最终并查集只有一个根结点,


(3)判断顶点数是否等于边数加1,如果不等,则说明不是树。


(4)判断节点的入度是否<=1,如果大于1,则说明不是树;


(5)判断两个节点的父节点是否相等,如果相等,则不能构成树;


并查集的学习:并查集--学习详解 http://blog.csdn.net/shuangde800/article/details/7329843


Is It A Tree代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 120005
using namespace std;
int father[N], rank[N],in[N],out[N];
bool vis[N], isCircle;

void initSet(){
    for(int i=1; i<N; ++i){
        father[i]=i, rank[i]=0;
        in[i] = 0, out[i] = 0;
    }
}

int find(int x){
    int i, j = x;
    while(j!=father[j]) j=father[j];
    while(x!=j){
        i = father[x];
        father[x] = j;
        x = i;
    }
    return j;
}

void Union(int x, int y){
    int a = find(x);
    int b = find(y);
    if(a == b){
        isCircle = true;
        return;
    }
    if(rank[a] > rank[b])
        father[b] = a;
    else{
        if(rank[a] == rank[b])
            rank[b]++;
        father[a] = b;
    } 
}

int main(){
#ifdef LOCAL
    freopen("input.txt","r",stdin);
#endif
    int a,b,cas=1;
    bool flag=true;
    
    while(~scanf("%d %d",&a,&b) && a>=0 && b>=0){
        if(!a && !b){
            printf("Case %d is a tree.\n",cas++);
            continue;
        }

        int edge = 1;
        memset(vis, 0, sizeof(vis));
        flag = true;
        isCircle = false;
        initSet();


        int Max = a>b?a:b;
        int Min = a<b?a:b;

        if(a==b) flag=false;
        vis[a]=vis[b]=true;
        ++in[b];
        ++out[a];
        Union(a, b);

        while(~scanf("%d %d",&a,&b) && a && b){
            vis[a] = vis[b] = true;
            if(a==b) flag=false;
            if(Min > a) Min = a;
            if(Min > b) Min = b;
            if(Max < a) Max = a;
            if(Max < b) Max = b;

            ++in[b];
            if(in[b]>1) flag=false;

            ++edge;

            Union(a,b);
        }
        int numConnect=0, node=0;
        for(int i=Min; i<=Max; ++i) if(vis[i] ){
            ++node;
            if(father[i]==i)
                ++numConnect;
        }
        
        if(node!=edge+1) flag = false;

        if(flag && !isCircle && numConnect==1) printf("Case %d is a tree.\n", cas++);
        else printf("Case %d is not a tree.\n",cas++);
    }
    return 0;
}


—— 生命的意义,在于赋予它意义。

原创http://blog.csdn.net/shuangde800By D_Double










分享到:
评论

相关推荐

    hdu 1753 大明A+B

    现在,给你两个正的小数A和B,你的任务是代表大明计算出A+B的值。 Input 本题目包含多组测试数据,请处理到文件结束。 每一组测试数据在一行里面包含两个长度不大于400的正小数A和B。 Output 请在一行里面...

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

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

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

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

    ACM hdu 线段树题目+源代码

    从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。

    HDU刷题地图+精选详细笔记

    本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!

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

    标题这几题都是去判断树的,只是输出不一样 要用定义去做树,那肯定要知道树是什么 学习的时候很迷茫是没搞清楚大方向 什么是大方向呢? 两个字:图论 树肯定是图,但图不一定是树 搞清楚这么几个知识点就可以愉快的...

    hdu 3333 turing tree 解题报告

    Hdu 3333解题报告 题意描述: 给你n个数现在要你求在k个区间上[ai, bi]的不相同的数之和各是多少. N,000; k,000; 显然,这题不能用暴力来做。 这题我们选择用线段数来做。

    HDU ACM as easy as a+b

    acm hdu as easy as a+b

    HDU+2000-2099+解题报告

    ACM题库,一些题目和答案,以及解题报告,传上来共享

    HDU+2000-2099+解题报告.zip

    杭电OnlineJudge 200-2099的解题报告

    acm入门之枚举搜索

    acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs

    hdu 3341(ac自动机+状态压缩)

    hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...

    hdu 300+ AC 代码

    300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....

    hdu 1695 GCD(欧拉函数+容斥原理).docx

    hdu 1695 GCD(欧拉函数+容斥原理).docx

    HDUc++上机测试真题(错题汇集1

    2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文

    acm课件 HDU 算法大全

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

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

    hdu1250高精度加法

    HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高

    杭电ACMhdu1163

    杭电ACMhdu1163

Global site tag (gtag.js) - Google Analytics