nyoj42(并查集解决欧拉回路)

2024-09-08 02:48

本文主要是介绍nyoj42(并查集解决欧拉回路),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一笔画问题

时间限制: 3000 ms  |  内存限制: 65535 KB
难度: 4
描述

zyc从小就比较喜欢玩一些小游戏,其中就包括画一笔画,他想请你帮他写一个程序,判断一个图是否能够用一笔画下来。

规定,所有的边都只能画一次,不能重复画。

 

输入
第一行只有一个正整数N(N<=10)表示测试数据的组数。
每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<=2000),分别表示这个画中有多少个顶点和多少条连线。(点的编号从1到P)
随后的Q行,每行有两个正整数A,B(0<A,B<P),表示编号为A和B的两点之间有连线。
输出
如果存在符合条件的连线,则输出"Yes",
如果不存在符合条件的连线,输出"No"。
样例输入
2
4 3
1 2
1 3
1 4
4 5
1 2
2 3
1 3
1 4
3 4
样例输出
No
Yes

解题思路:是用并查集判断是否为联通路然后对每个点的度判断,如果两个都可以达成就输出“yes”否则输出“no”;

代码如下:

    #include <stdio.h>  #include <string.h>  #define MAX  1002  int degree[MAX];  int map[MAX];  void init(int n)  //点的初始化,每个点的根节点就是自己{  int i=0;  for(i=1;i<=n;i++)  map[i]=i;  }  int find(int i)  //查找该节点的最终根节点{  return (map[i]==i)?i:find(map[i]);  }  int main()  {  int n,k,i,j,q,a,b;  int  flage,cnt;  scanf("%d",&k);  while(k--)  {  scanf("%d%d",&n,&q);  flage=0;  memset(degree,0,sizeof(degree));  init(n); //初始化 for(i=0; i<q; i++)  {  scanf("%d %d",&a,&b);  degree[a]++;   //计算每个顶点的度;  degree[b]++;  map[find(a)]=map[find(b)];  //连接点和点成为一棵二叉树}  cnt=0;  for(i=1;i<=n;i++)  //计算一个图中有几个集合  {                    if(map[i]==i)  //即判断一个图是否连通,如果联通有且只有最后一个点的值为自己cnt++;  }  if(cnt!=1)  {  printf("No\n");continue;  }  for(i=1; i<=n; ++i)  {  if(degree[i]%2)  //计算每个点的度flage++;   //如果为欧拉回路的条件是每个点的度为偶数或者是开始和结尾的点mol2后和为2}  if((flage==0||flage==2))  printf("Yes\n");  else  printf("No\n");  }  return 0;  }  

//AC



这篇关于nyoj42(并查集解决欧拉回路)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1146896

相关文章

如何解决线上平台抽佣高 线下门店客流少的痛点!

目前,许多传统零售店铺正遭遇客源下降的难题。尽管广告推广能带来一定的客流,但其费用昂贵。鉴于此,众多零售商纷纷选择加入像美团、饿了么和抖音这样的大型在线平台,但这些平台的高佣金率导致了利润的大幅缩水。在这样的市场环境下,商家之间的合作网络逐渐成为一种有效的解决方案,通过资源和客户基础的共享,实现共同的利益增长。 以最近在上海兴起的一个跨行业合作平台为例,该平台融合了环保消费积分系统,在短

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

poj 1182 并查集 食物链类

题意: 有n只动物,分别编号1....n。所有动物都属于A,B,C中的一种,已知A吃B,B吃C,C吃A。 按顺序给出下面两种共K条信息: 1. x 和 y 属于同一类。 2. x 吃 y 。 然而这些信息可能会出错,有可能有的信息和之前给出的信息矛盾,也有的信息可能给出的 x 和 y 不在n的范围内。 求k条信息中有多少条是不正确的。 解析: 对于每只动物,创建3个元素 i

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

【VUE】跨域问题的概念,以及解决方法。

目录 1.跨域概念 2.解决方法 2.1 配置网络请求代理 2.2 使用@CrossOrigin 注解 2.3 通过配置文件实现跨域 2.4 添加 CorsWebFilter 来解决跨域问题 1.跨域概念 跨域问题是由于浏览器实施了同源策略,该策略要求请求的域名、协议和端口必须与提供资源的服务相同。如果不相同,则需要服务器显式地允许这种跨域请求。一般在springbo

POJ1988带权并查集

M u v 将u所在的堆移动到v所在的堆的上面 C u 求u的下面有多少块 带权并查集 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;i

POJ1703带权并查集

D: u v  u与v在不同的集合 A: u v  查询u与v的关系 1)压缩路径过程        fu->root   0  1  u-fu 0                 0  1   1                 1  0 2)合并过程 fu->fv      u->fu   0 1   v->fv 0            1 0 1            0

速盾高防cdn是怎么解决网站攻击的?

速盾高防CDN是一种基于云计算技术的网络安全解决方案,可以有效地保护网站免受各种网络攻击的威胁。它通过在全球多个节点部署服务器,将网站内容缓存到这些服务器上,并通过智能路由技术将用户的请求引导到最近的服务器上,以提供更快的访问速度和更好的网络性能。 速盾高防CDN主要采用以下几种方式来解决网站攻击: 分布式拒绝服务攻击(DDoS)防护:DDoS攻击是一种常见的网络攻击手段,攻击者通过向目标网

Jenkins 插件 地址证书报错问题解决思路

问题提示摘要: SunCertPathBuilderException: unable to find valid certification path to requested target...... 网上很多的解决方式是更新站点的地址,我这里修改了一个日本的地址(清华镜像也好),其实发现是解决不了上述的报错问题的,其实,最终拉去插件的时候,会提示证书的问题,几经周折找到了其中一遍博文