NYOJ129 决策树 【并检查集合】

NYOJ129 决策树 【并检查集合】

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

树的判定

时间限制:
1000 ms  |  内存限制:
65535 KB
难度:
4

描写叙述

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. 

NYOJ129 决策树 【并检查集合】

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.

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

The number of test cases will not more than 20,and the number of the node will not exceed 10000.

The inputs will be ended by a pair of -1.

输出
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).

例子输入
6 8  5 3  5 2  6 4 5 6  0 08 1  7 3  6 2  8 9  7 5 7 4  7 8  7 6  0 03 8  6 8  6 4 5 3  5 6  5 2  0 0-1 -1
例子输出
Case 1 is a tree.Case 2 is a tree.Case 3 is not a tree.
来源
POJ
上传者
张云聪

题意:推断一个有向图是否是树。

题解:假设一个图是树。那么必须满足下面情况: 

1、树的数量不能大于1。空树也是树。

2、节点入度数不能大于1;

3、不能成环,比方一棵树的叶子节点指向根节点就是非法的;

4、自环是非法的。

#include <stdio.h>
#include <string.h>

#define maxn 10010

int pre[maxn];
bool vis[maxn];

int unionFind(int k){
	int a = k, b;
	while(pre[k] != -1) k = pre[k];
	while(a != k){
		b = pre[a];
		pre[a] = k;
		a = b;
	}
	return k;
}

int main() {
	// freopen("stdin.txt", "r", stdin);
	memset(pre, -1, sizeof(pre));
	int u, v, cas = 1, ok = 1, count = 0;
	while(scanf("%d%d", &u, &v) != EOF) {
		if(u < 0) break;
		if(!(u | v)) {
			printf("Case %d ", cas++);
			if(count > 1) ok = 0;
			if(ok) printf("is a tree.\n");
			else printf("is not a tree.\n");
			memset(pre, -1, sizeof(pre));
			memset(vis, 0, sizeof(vis));
			count = 0; ok = 1; continue;
		}
		if(!ok) continue;

		if(!vis[u]) {
			vis[u] = 1; ++count;
		}
		if(!vis[v]) {
			vis[v] = 1; ++count;
		}
		if(pre[v] != -1 || u == v) {
			ok = 0; continue;
		}
		u = unionFind(u);
		if(u == v) {
			ok = 0; continue;
		}
		pre[v] = u; --count;
	}
	return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117745.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 使用decode函数

    使用decode函数Decode函数使用:Oracle的decode函数蛮有意思,是oracle独有的,国际标准SQL中并没有decode函数。语法DECODE(col|expression,search1,result1[,search2,result2,…,][,default])例子SELECTproduct_id,DECODE(warehouse_id,1…

  • 控件anchor和dock属性_控件的常用属性

    控件anchor和dock属性_控件的常用属性在设计窗体时,这两个属性特别有用,如果用户认为改变窗口的大小并不容易,应确保窗口看起来显示的不是那么乱,并编写很多代码来实现这个效果,许多程序解决这个问题都是禁止给窗口重新设置大小这显然是解决问题的最简单的方法,但不是最好的方法,因此引入了Anchor和Dock属性。1、Anchor属性用于指定在用户重新设置窗口的大小时控件应该如何响应,可以指定如果控件重新设置了大小,就根据控件的边界去锁

  • 如何创建conda环境_conda安装Python包

    如何创建conda环境_conda安装Python包Pycharm中如何使用新建的conda环境?

  • centos7重启apache、nginx、mysql、php-fpm命令

    centos7重启apache、nginx、mysql、php-fpm命令

    2021年10月27日
  • HashMap的数据结构

    前提:主要数据结构:数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。数组数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;链表链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N)。链表的特点是:寻址困难,插入和删除容易。哈希表那么我…

  • BetterIntelliJ-1.19 通用激活码-激活码分享

    (BetterIntelliJ-1.19 通用激活码)2021最新分享一个能用的的激活码出来,希望能帮到需要激活的朋友。目前这个是能用的,但是用的人多了之后也会失效,会不定时更新的,大家持续关注此网站~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号