Hdu.1325.Is It A Tree?(并查集)

时间:2022-09-20 19:45:22

Is It A Tree?

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 16702    Accepted Submission(s): 3761

Problem Description
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.Hdu.1325.Is It A Tree?(并查集)Hdu.1325.Is It A Tree?(并查集)Hdu.1325.Is It A Tree?(并查集)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.
 #include<stdio.h>
#include<string.h>
const int M = + ;
int f[M] ;
int path[M] ;
int in[M] ;
bool vis[M] ; int Union (int x)
{
return x == f[x] ? x : f[x] = Union (f[x]) ;
}
int main ()
{
freopen ("a.txt" , "r" , stdin ) ;
int u , v ;
int cas = ;
while (~ scanf ("%d%d" , &u , &v)) {
if (u < || v < ) break ;
for (int i = ; i < M ; i ++) f[i] = i ;
memset (vis , , sizeof(vis));
memset (in , , sizeof(in)) ;
int tot = ;
if (!vis[u]) {
vis[u] = ;
path[tot ++] = u ;
}
if (!vis[v]) {
vis[v] = ;
path[tot ++] = v ;
}
in[v] ++ ;
// printf ("%d ----> %d\n" , u , v);
int x = Union (u) , y = Union (v) ;
f[y] = x ;
if (u != && v != ) {
while () {
scanf ("%d%d" , &u , &v) ;
// printf ("%d ----> %d\n" , u , v);
if (u == && v == ) break ;
if (!vis[u]) {
vis[u] = ;
path[tot ++] = u ;
}
if (!vis[v]) {
vis[v] = ;
path[tot ++] = v ;
}
in[v] ++ ;
int x = Union (u) , y = Union (v) ;
f[y] = x ;
}
for (int i = ; i < tot ; i ++) Union (path[i]) ;
// for (int i = 0 ; i < tot ; i ++) printf ("%d " , path[i]) ; puts ("") ;
// for (int i = 0 ; i < tot ; i ++) printf ("%d " , in[path[i]]); puts ("") ;
// for (int i = 0 ; i < tot ; i ++) printf ("%d " , f[path[i]]) ; puts ("") ;
bool flag = ;
int cnt = ;
int father = f[path[]] ;
for (int i = ; i < tot && !flag; i ++)
if (f[path[i]] != father )
flag = ; for (int i = ; i < tot && !flag ; i ++) {
if (in[path[i]] > ) flag = ;
if (in[path[i]] == ) cnt ++ ;
if (cnt > ) flag = ;
}
if (cnt == ) flag = ;
// printf ("flag = %d\n" , flag );
if (flag) printf ("Case %d is not a tree.\n" , cas ++);
else printf ("Case %d is a tree.\n" , cas ++) ;
}
else printf ("Case %d is a tree.\n" , cas ++) ;
}
return ;
}

检查入度,和每个结点的祖先。

终于解决了并查集压缩路径的不完全的问题。hahahaha。。。

另外没有结点,也被认为是树。

Hdu.1325.Is It A Tree?(并查集)的更多相关文章

  1. hdu 1325 Is It A Tree&quest; 并查集

    Is It A Tree? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Tot ...

  2. hdu 5458 Stability&lpar;树链剖分&plus;并查集&rpar;

    Stability Time Limit: 3000/2000 MS (Java/Others)    Memory Limit: 65535/102400 K (Java/Others)Total ...

  3. &lbrack;HDU 3712&rsqb; Fiolki &lpar;带边权并查集&plus;启发式合并&rpar;

    [HDU 3712] Fiolki (带边权并查集+启发式合并) 题面 化学家吉丽想要配置一种神奇的药水来拯救世界. 吉丽有n种不同的液体物质,和n个药瓶(均从1到n编号).初始时,第i个瓶内装着g[ ...

  4. HDU 5606 tree 并查集

    tree 把每条边权是1的边断开,发现每个点离他最近的点个数就是他所在的连通块大小. 开一个并查集,每次读到边权是0的边就合并.最后Ans​i​​=size[findset(i)],size表示每个并 ...

  5. tree&lpar;并查集&rpar;

    tree Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submis ...

  6. hdu 5652 India and China Origins 并查集

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5652 题目大意:n*m的矩阵上,0为平原,1为山.q个询问,第i个询问给定坐标xi,yi,表示i年后这 ...

  7. Is It A Tree&quest;&lpar;并查集&rpar;

    Is It A Tree? Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 26002   Accepted: 8879 De ...

  8. CF109 C&period; Lucky Tree 并查集

    Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal re ...

  9. hdu - 1829 A Bug&&num;39&semi;s Life &lpar;并查集&rpar;&amp&semi;&amp&semi;poj - 2492 A Bug&&num;39&semi;s Life &amp&semi;&amp&semi; poj 1703 Find them&comma; Catch them

    http://acm.hdu.edu.cn/showproblem.php?pid=1829 http://poj.org/problem?id=2492 臭虫有两种性别,并且只有异性相吸,给定n条臭 ...

随机推荐

  1. jquery函数理解与运用

    javascript中有多种不用的方式去理解函数,函数类似于我们以前学过的数学函数,但是在程序设计中,我是按照下面的方式进行理解: 函数的理解: 函数是一个代码块,内容被包含在函数内,通常我们是把一些 ...

  2. &period;Net组件程序设计之远程调用(二)

    .Net组件程序设计之远程调用(二) 激活模式 引用封送对象激活类型两种, 一种是客户端激活类型,一种是服务器端激活. 客户端激活对象 客户端激活方式:当客户端创建一个远程对象时,客户端得到的是一个新 ...

  3. Windows上python的virtualenv 安装及使用

    源地址:http://blog.csdn.net/liuchunming033/article/details/46008301 VirtualEnv可以方便的解决不同项目对类库的依赖问题. 现实测试 ...

  4. 机器学习:异常检测算法Seasonal Hybrid ESD及R语言实现

    Twritters的异常检测算法(Anomaly Detection)做的比较好,Seasonal Hybrid ESD算法是先用STL把序列分解,考察残差项.假定这一项符合正态分布,然后就可以用Ge ...

  5. 45&period; Singleton类的C&plus;&plus;&sol;C&num;实现&lbrack;Singleton&rsqb;

    [题目] 设计一个类,我们只能生成该类的一个实例. [分析] 单例模式的意图是保证一个类仅有一个实例,并提供一个访问它的全局访问点.让类自身负责保存它的唯一实例.这个类可以保证没有其他实例可.以被创建 ...

  6. eclipse的shell相关插件

    1.Easy Shell a. 功能 可以在Eclipse IDE里选中一个文件或目录,利用Easy Sehll直接跳转到Sehll窗口,很方便 b. 安装 Help - Install New So ...

  7. jQuery on&lpar;&rpar;方法使用

    jQuery on()方法 基本语法: 语法结构一: $(selector).on(event,function) 语法结构二: $(selector).on(events,[selector],[d ...

  8. EFCore中SQLSERVER 2008 的分页问题

    自SQLSERVER 2012起新增了 Offset Fetch 语法,因此EFCore默认是以此语法生成相应的分页语句的. 如果我们的目标数据库低于 2012,那么EFCore默认生成的语句在执行的 ...

  9. laravel的foreach

    1.控制器 2.模板

  10. input 标签禁止输入

    1.鼠标可以点击输入框,但是不能输入 readonly 例如: <input class="layui-input" readonly > 2.鼠标点击输入框出现禁用图 ...