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)


相关推荐

  • potplayer 64位 官网下载地址

    potplayer 64位 官网下载地址potplayer64位最新官网下载地址链接:https://gsf-fl.softonic.com/f94/2ec/be06ec8a283bee92cda70eb3ede9c661d0/PotPlayerSetup64.exe?Expires=1585679112&Signature=cff21a190f0fcb9c61356f8eca9b8155ed6afc48&ur…

  • D3旭日图_日新图

    D3旭日图_日新图本文将介绍D3旭日图的画法下面我们先来看看结果展示html代码<!DOCTYPEhtml><html><head><metacharset=”utf-8″><title>Sequencessunburst</title><scriptsrc=”js/d3.min.js…

  • 给定一个n个正整数组成的数组_求数组最小差值最优算法

    给定一个n个正整数组成的数组_求数组最小差值最优算法给定长度为 N 的数列 A,然后输入 M 行操作指令。第一类指令形如 C l r d,表示把数列中第 l∼r 个数都加 d。第二类指令形如 Q x,表示询问数列中第 x 个数的值。对于每个询问,输出一个整数表示答案。输入格式第一行包含两个整数 N 和 M。第二行包含 N 个整数 A[i]。接下来 M 行表示 M 条指令,每条指令的格式如题目描述所示。输出格式对于每个询问,输出一个整数表示答案。每个答案占一行。数据范围1≤N,M≤105,|d|≤10000,|A[i]|≤109输

  • 前端_单页面开发_web前端框架

    前端_单页面开发_web前端框架   web移动端单页面开发,可适用于web端直接开发。本例需要使用require.js帮助实现。   单页面开发个人理解:对一个项目里面的所有html文件都拥有同一个url,通过hash值的改变来促发页面的跳转(hash为url后面的内容,如下面的#red和#green就是hash),如两个页面的url分别为(http://localhost:8000/views/index.htm…

    2022年10月13日
  • Swift4 String截取字符串

    Swift4 String截取字符串varstr1="AlexanderYeah";//1截取字符串的第一种方式//prefix截取前3个字符串varstr2=str1.prefix(3);print(str2);//suffix截取后3个字符串varstr3=str1.suffix(3);print(str3);//2截取一个范围的字符串//从0开始到倒数第二位结…

  • shuffleNet_shuffer

    shuffleNet_shuffer目录分组卷积分组卷积的矛盾——计算量分组卷积的矛盾——特征通信channelshuffleShuffleNetV1ShuffleNet基本单元ShuffleNet网络结构对比实验ShuffleNetV2设计理念网络结构对比实验分组卷积Groupconvolution是将输入层的不同特征图进行分组,然后采用不同的卷积核再对各个组进行卷积,这样会降低卷积的计算量。因为一般的卷积都是在所有的输入特征图上做卷积,可以说是全通道卷积,这是一种通道密集连.

发表回复

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

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