NYOJ-129 并查集

时间:2022-09-04 15:22:27

这个题基本上是并查集稍微一变, 只是加了一些判断条件而已,就是将点合并成树, 最后遍历一下, 统计一下有多少棵树, 如果不是1的话, 肯定不是树,所以,可以根据这个来判断

 #include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std; const int MAX = ;
int f[MAX], IN[MAX], k = , sum = ;//IN表示节点的入度
bool visit[MAX];/*标记数组中的点是否存在, 就是是否是图中的点,
只要是输入的点, 其visit全部为true*/
bool flag;//标记是否是树
//初始化
void init()
{
for(int i = ; i < MAX; i++)
f[i] = i;
}
//找到它的父亲
int getf(int i)
{
if(i != f[i])
{
f[i] = getf(f[i]);//路径压缩
}
return f[i];
}
//合并函数,
void merge(int i, int j)
{
int t1 = getf(i);
int t2 = getf(j);
if(t1 != t2)
{
f[t2] = t1;
}
else
flag = false;//如果输入的点已经存在
} int main()
{
int x, y;
flag = true;
int max_num = ;
memset(f, , sizeof(f));
memset(IN, , sizeof(IN));
memset(visit, false, sizeof(visit));
init();
while(scanf("%d %d", &x, &y))
{
if(x == - && y == -)
break;
if(x == && y == )
{
sum = ;
for(int i = ; i <= max_num; i++)
{
if(visit[i] && i == f[i])//如果是根节点, 也就是树的个数
sum++;
}
for(int i = ; i <= max_num; i++)
if(visit[i] && IN[i] > )//如果一个节点的入度大于1
flag = false;
if(sum > )
flag = false;
if(flag)
printf("Case %d is a tree.\n", ++k);
else
printf("Case %d is not a tree.\n", ++k);
memset(f, , sizeof(f));
memset(visit, false, sizeof(visit));
memset(IN, , sizeof(IN));
flag = true;
init();
}
else
{
if(!flag)
continue;
max_num = max(max_num, max(x, y));
visit[x] = true;//标记此点在图中
visit[y] = true;
IN[y]++;//将第二个点的入度加一
merge(x, y);
}
}
return ;
}

NYOJ-129 并查集的更多相关文章

  1. NYOJ 129 树的判定 (并查集)

    题目链接 描述 A tree is a well-known data structure that is either empty (null, void, nothing) or is a set ...

  2. Nyoj 布线问题&lpar;并查集&amp&semi;&amp&semi;图论&rpar;

    描述南阳理工学院要进行用电线路改造,现在校长要求设计师设计出一种布线方式,该布线方式需要满足以下条件:1.把所有的楼都供上电.2.所用电线花费最少   输入 第一行是一个整数n表示有n组测试数据.(n ...

  3. nyoj 1022 合纵连横 经典并查集

    思路:关键在于并查集的删点操作. 给每个诸侯国一个另外的编号,比如box[i]表示诸侯国i现在处于第box[i]个联盟,可以随时改变它的联盟编号,并且让box[i] = k, 实现删除操作.以前联盟中 ...

  4. NYOJ 208 Supermarket (模拟&plus;并查集)

    题目链接 描述 A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Pr ...

  5. NYOJ 1022 合纵连横 (并查集)

    题目链接 描述 乱世天下,诸侯割据.每个诸侯王都有一片自己的领土.但是不是所有的诸侯王都是安分守己的,实力强大的诸侯国会设法吞并那些实力弱的,让自己的领土面积不断扩大.而实力弱的诸侯王为了不让自己的领 ...

  6. NYOJ 42 一笔画问题 (并查集&plus;欧拉回路 )

    题目链接 描述 zyc从小就比较喜欢玩一些小游戏,其中就包括画一笔画,他想请你帮他写一个程序,判断一个图是否能够用一笔画下来. 规定,所有的边都只能画一次,不能重复画.   输入 第一行只有一个正整数 ...

  7. nyoj 711 枚举&plus;并查集

     #include<stdio.h>//从大到小不断枚举边直到找到s-t的路径,判断从s可以到t可以用并查集来判断 #include<stdlib.h>//枚举最大的一条边肯定 ...

  8. poj 1182 食物链 &amp&semi;amp&semi;&amp&semi;amp&semi; nyoj 207(种类并查集)

    食物链 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 52414   Accepted: 15346 Description ...

  9. nyoj 209 &plus; poj 2492 A Bug&&num;39&semi;s Life &lpar;并查集&rpar;

    A Bug's Life 时间限制:1000 ms  |  内存限制:65535 KB 难度:4   描述 Background  Professor Hopper is researching th ...

  10. nyoj 1022 合纵连横 &lpar;并查集&lt&semi;节点删除&gt&semi;&rpar;

    合纵连横 时间限制:1000 ms  |  内存限制:65535 KB 难度:3   描述 乱世天下,诸侯割据.每个诸侯王都有一片自己的领土.但是不是所有的诸侯王都是安分守己的,实力强大的诸侯国会设法 ...

随机推荐

  1. jquery的事件命名空间详解

    jquery现在的事件API:on,off,trigger支持带命名空间的事件,当事件有了命名空间,就可以有效地管理同一事件的不同监听器,在定义组件的时候,能够避免同一元素应用到不同组件时,同一事件类 ...

  2. 【转】天啦噜!原来Chrome自带的开发者工具还能这么用!&lpar;提升JS调试能力的10个技巧&rpar;

    天啦噜!原来Chrome自带的开发者工具还能这么用! (提升JS调试能力的10个技巧)   Chrome自带开发者工具.它的功能十分丰富,包括元素.网络.安全等等.今天我们主要介绍JavaScript ...

  3. noip2015-day1-t2

    题意:有n个同学(编号为1到n)正在玩一个信息传递的游戏.在游戏里每人都有一个固定的信息传递对象,其中,编号为i的同学的信息传递对象是编号为Ti同学.游戏开始时,每人都只知道自己的生日.之后每一轮中, ...

  4. 防DDOS攻击

    /ip firewall filter add chain=forward connection-state=new action=jump jump-target=block-ddos add ch ...

  5. cocos2dx3&period;4 保存json文件

    头文件: #include "json/document.h" #include "json/stringbuffer.h" #include "js ...

  6. 设计模式之装饰者模式(Decorator Pattern)

    一.什么是装饰者模式? 装饰者模式能够完美实现“对修改关闭,对扩展开放”的原则,也就是说我们可以在不修改被装饰者的前提下,扩展被装饰者的功能. 再来看看我们的文件操作代码: 1 InputStream ...

  7. C&num;获取窗口,模拟按键操作

    C#获取窗口,模拟按键操作,实现计算器模拟操作.首先引用. using System.Runtime.InteropServices; 使用DllImport引入两个函数: // Get a hand ...

  8. 人人必知的10个jQuery小技巧

    收集的10个 jQuery 小技巧/代码片段,可以帮你快速开发. 1.返回顶部按钮 你可以利用 animate 和 scrollTop 来实现返回顶部的动画,而不需要使用其他插件. // Back t ...

  9. 常用SQL语句集合

    一.数据定义 1.创建新数据库:CREATE DATABASE database_name2.创建新表:CREATE TABLE table_name (column_name datatype,co ...

  10. HDOJ2870 Largest Submatrix

    一道\(DP\) 原题链接 发现只有\(a,b,c\)三种情况,所以直接初始化成三个\(01\)方阵,找最大子矩阵即可. 我是先初始化垂直上的高度,然后对每一行处理出每个点向左向右的最大延伸,并不断计 ...