当前位置: 首页 > 编程日记 > 正文

1126 Eulerian Path

主要考英语或者数学基础。

一幅连通图的奇点个数为0或2时才能够被一笔画。

连通图的判断用DFS来计数。

连通图+0个奇点:Eulerian

连通图+2个奇点:semi-Eulerian

非连通图/连通图+其他数量的奇点:non-Eulerian

AC代码

#include<cstdio>
#include<iostream>
#include<set>
#include<vector>
#include<map>
#include<algorithm>using namespace std;const int SUP = 100000000;
const int maxn = 510;int degree[maxn] = {0};int vNum,eNum;vector<int> G[maxn];int cnt = 0;
bool vis[maxn] = {0};void DFS(int root){vis[root] = 1;cnt ++;for(int i=0;i<G[root].size();i++){int j = G[root][i];if(vis[j]==0)DFS(j);}
}int main(){cin>>vNum>>eNum;for(int i=0;i<eNum;i++){int v1,v2;cin>>v1>>v2;degree[v1]++;degree[v2]++;G[v1].push_back(v2);G[v2].push_back(v1);}int oddN = 0;for(int i=1;i<=vNum;i++){if(degree[i]%2!=0){oddN ++;}printf("%d%s",degree[i],i==vNum?"\n":" ");}DFS(1);if(oddN==0&&cnt==vNum)printf("Eulerian\n");else if(oddN==2&&cnt==vNum)printf("Semi-Eulerian\n");else printf("Non-Eulerian");return 0;
}

相关文章:

各种小的 dp (精)

Q~ 抛一枚硬币 n 次&#xff0c;每次可能是正面或者反面向上&#xff0c;求没有连续超过 k 次硬币向上的方案数 A &#xff1a; dp[ i ] 表示到 i 位置的方案数&#xff0c; 1 . 当 i < k 时&#xff0c; dp[i] dp[i-1]*2 2 . 当 i k 时&#xff0c; dp[i] dp[i-1]*2 - 1…

写给还在大学的兄弟姐妹

看到软件专业毕业生之一个月攻略 这篇文章之后&#xff0c;忽然想起了自己两个多月前找工作时的写的一篇文章&#xff0c;便拿出来与大家分享。这仅是个人的一些看法&#xff0c;不正确之处还请各位指出&#xff0c;有砖尽管拍。 基础很重要 许多企业招聘&#xff0c;要求大学…

grunt学习

1、http://javascript.ruanyifeng.com/tool/grunt.html Grunt&#xff1a;任务自动管理工具 2、转载于:https://www.cnblogs.com/king-bj/p/4322794.html

IP地址和MAC地址

MAC地址又称硬件地址&#xff0c;是MAC帧的头部&#xff0c;在数据链路层只能看见MAC地址。 IP地址是逻辑地址&#xff0c;是IP数据报的头部&#xff0c;路由器根据IP地址进行路由选择。 IP地址为4个字节32位&#xff0c;编制经历了3个历史阶段。 MAC地址为6个字节48位。

ie9下console不兼容的问题

最近在调整项目在ie9下的展示问题&#xff0c;发现在ie9下&#xff0c;js文件不执行&#xff0c;打开控制台才执行&#xff0c;原因是ie9不支持console&#xff0c;以下给出两种解决方案&#xff1a;1. 在webpack.prod.conf.js 中添加并修改js插件配置项&#xff08;我用的是we…

[转载] linux、Solaris下xdmcp远程桌面服务

原文链接 http://youlvconglin.blog.163.com/blog/static/52320420106243857254/ 使用图形界面远程登录linux和Solaris&#xff0c;首先要在服务端开启xdmcp服务&#xff0c;windows下使用xmanager连接 Ubuntu下则使用下默认也安装了该客户端&#xff0c;一次打开[应用程序]-[…

3.2.4 控制图层显示的范围

为了是地图更加简洁 和 减小地图负载 &#xff0c;达到分级显示某些图层的效果&#xff0c;应该为每一个图层设置 合理的 可见比例尺范围。1 begin2 3 aeMapMain.Layer[2].MaximumScale :500000;//最大可见比例尺 分母4 aeMapMain.Layer[2].MinimumScale :1000000;//最小可见比…

1103 Integer Factorization 需再做

本题是典型的DFS剪枝 我对DFS有了更深的认识&#xff1a;整个过程就是一片森林(根节点不唯一)的生长&#xff0c;到了界限就得到结果并返回或者得不到结果也返回&#xff0c;DFS的参数存放的是所有需要积累的变量。 提示&#xff1a; 1. 最外层的while或者for可以看成是一个…

POJ1001--Exponentiation(幂计算)翻译

Exponentiation幂计算Time Limit: 500MSMemory Limit: 10000KTotal Submissions: 141868Accepted: 34673 Description 描述 Problems involving the computation of exact values of very large magnitude and precision are common. 高精度、大数值的计算问题是很常见的&…

datatable无法设置横向滚动条(设置无效)

datatable设置横向滚动条无效 js如下&#xff1a; 页面如下&#xff1a; 设置 scrollx 属性为true时&#xff0c;还需在 table 添加 style"white-space: nowrap; "最终效果&#xff1a; 转载于:https://www.cnblogs.com/renzp/p/10069594.html

水晶报表导出数据并实现打印

要在里一个页面上进行操作 ReportDocument rdocument new ReportDocument(); //公用打印方法 ExportCrystalL ExCrystal new ExportCrystalL(); User u new User(); #region 加载页面 protected void Page_Load(object sender, EventArgs e) { if (!IsPostB…

1130 Infix Expression

考察&#xff1a;DFS进行中序遍历。 注意&#xff1a;给除了根节点以外的父节点加左右括号。 AC代码 #include<cstdio> #include<iostream> #include<set> #include<vector> #include<map> #include<algorithm> #include<cmath> …

学习笔记之vue根据权限动态添加路由

路由守卫判断 router.beforeEach((to, from, next) > {if (to.path /login) {sessionStorage.removeItem(user);}if (!user && to.path ! /login&&location.search ! ?validate) {next({ path: /login })} else {next()} }) 复制代码 点击登陆后&#xff…

javascript重置(base层)(。。。。不完整)

1、nextSibling浏览器兼容问题 <ul><li id"item1"></li><li id"item2"></li><li id"item3"></li> </ul> var item1document.getElementById("item1"); alert(item1.nextSibling.id);…

java myeclipse jar 导出问题

1.工程 jdk要和实际jdk最好一个版本;2.有外部导入的jar,导出时应用manifest&#xff0c;设置外部引用JAR。例如&#xff1a;Manifest-Version: 1.0 Sealed: true Class-Path: lib/log4j-1.2.8.jar lib/xercesImpl.jar Main-Class: com.unimoco.mmsplatform.handler.MMSMOCenter…

漫谈回溯(未完待续)

将不使用优化算法、直接用朴素算法来解决问题的做法称为暴力法。 回溯是带优化的穷举。 回溯是具有界限函数的深度优先搜索。

sendStickyBroadcast和sendStickyOrderedBroadcast

sendStickyBroadcast和sendStickyOrderedBroadcast - 牛仔的移动开发博客 - 博客频道 - CSDN.NET sendStickyBroadcast和sendStickyOrderedBroadcast发出的广播会一直滞留&#xff08;等待&#xff09;&#xff0c;以便有人注册这则广播消息后能尽快的收到这条广播。其他功能与…

固定资产打印条码标签应用方案

条码在固定资产管理中的应用方案&#xff1a; 应用客户案例&#xff1a; 河南省交通规划勘察设计院 黄河水文勘察测绘局 以实物管理为基础&#xff0c;以条码技术的应用为特点。通过先进的条码技术对固定资产实物从购置、领用、转移、盘点、清理到报废等方面进行全方位准确监管…

有关于诚信:唐骏学历门

提高造假的成本 - 南桥的博客 唐骏的学历门曝光后&#xff0c;我回想起过去的一件往事来。我读博士的时候&#xff0c;有人找我合作&#xff0c;在其介绍材料里写“博士”&#xff0c;我赶紧写信纠正&#xff0c;说自己是“博士生”&#xff08;doctoral student)&#xff0c;而…

1115 Counting Nodes in a BST

我的DFS void DFS(Node* root){if(rootNULL)return;if(root->lchild){root->lchild->layer root->layer1;cnt[root->lchild->layer] ;maxLayer max(maxLayer,root->lchild->layer);DFS(root->lchild);}if(root->rchild){root->rchild->…

必会重构技巧:使用多态替换条件

使用多态替换条件&#xff1a;指在进行类型检查和执行某些类型操作时&#xff0c;最好将算法封装在类中&#xff0c;并且使用多态来对代码中的调用进行抽象 举例理解&#xff1a;看定义可能比较迷糊&#xff0c;其实说的简单一点&#xff0c;对于使用分支语句并且分支条件是和…

深度分析Java的枚举类型——枚举的线程安全性及序列化问题

点击关注&#xff0c;快速进阶高级架构师作者&#xff1a;Hollis写在前面&#xff1a;Java SE5提供了一种新的类型-Java的枚举类型&#xff0c;关键字enum可以将一组具名的值的有限集合创建为一种新的类型&#xff0c;而这些具名的值可以作为常规的程序组件使用&#xff0c;这是…

1081 Rational Sum 有理数类型题处理 需再做

一、有理数结构体的几个约束 struct fraction{LL up,down;fraction(LL _up,LL _down):up(_up),down(_down){} }; &#xff08;1&#xff09;如果这个有理数是0&#xff0c;则让分子为0&#xff0c;分母为1(这方便后来输出时归于整数一类) &#xff08;2&#xff09;如果这个…

LeetCode 191 Number of 1 Bits

LeetCode 191 Number of 1 Bits 解法一(较为传统都解法)&#xff1a;使用将n不断右移&#xff0c;并与1想&得到1的个数&#xff1b;&#xff08;也有使用除法/2的&#xff0c;明显除法的运行效率要低于位移&#xff09; 时间复杂度:0(logn) 1 int hammingWeight(uint32_t …

某网站破解备忘

某网站采用了多种反破解手段&#xff0c;特此开贴记录分析破解过程。 工具和参考 awesome-java-crawler - 我收集的爬虫相关工具和资料 java-curl - 本人写的java HTTP库&#xff0c;可用来替换chrome网络后端&#xff0c;更方便控制底层行为&#xff0c;如缓存、代理、监控、修…

用XML反序列化快速完成ASP.NET配置文件

一般来说&#xff0c;asp.net的配置文件用web.config就可以解决&#xff0c;但是有时候我们希望完全用自己的形式来配置某些东西&#xff0c;比如希望用下面的形式来配置一个站点的所有有message。<Messages> <Message ID"ID1">Message1</Message&…

1088 Rational Arithmetic

本题需要具备有理数处理相关知识。 本次收获(错点) &#xff08;1&#xff09;在化简求最大公约数时&#xff0c;忘记给传入的分子加绝对值 &#xff08;2&#xff09;把除法错写成乘法&#xff0c;自己设计测试用例才测出orz AC代码 #include<cstdio> #include<…

CesiumLab V1.2 新功能 倾斜数据处理

一转眼又是一周的时间&#xff0c;我们的实验室功能又强大了。 照旧我们先放毒&#xff0c;放图&#xff0c;图&#xff0c;太晚了&#xff0c;字都敲不到一起了lod以及包围盒大雁塔实例&#xff0c;按楼层单体化倾斜数据处理参数设置 简单介绍一下 CesiumLab 的 Osgb倾斜数据转…

参加海峡两岸城市地理信息系统论坛2010 年会(一张图、规划信息化和空间句法的碎碎念)...

上周末去清华建筑学院开了个会&#xff0c;叫做海峡两岸城市地理信息系统论坛2010 年会&#xff0c;主题很大&#xff0c;但是内容比较集中一些&#xff0c;就是围绕着GIS与城市规划。一天下来听了20个报告&#xff0c;挺佩服主办方的时间控制&#xff0c;这么密集的报告&#…

hdu 2087 剪花布条

http://acm.hdu.edu.cn/showproblem.php?pid2087 水题&#xff0c;注意细节就可以了。 代码如下&#xff1a; #include<iostream> #include<string>using namespace std;int main() {string s1,s2;while(cin>>s1&&s1!"#"){cin>>s2;…