传送门:http://codeforces.com/contest/788/problem/B

好题!好题!

首先图不连通的时候肯定答案是0,我们下面讨论图联通的情况

首先考虑,如果我们每条边都经过两边,那么肯定是可行的

因为这样相当于把每条边复制一遍,然后问图中是否存在欧拉路径

既然每条边都出现了两遍,那么所有点的度数一定都是偶数,所以肯定有欧拉路径

现在考虑将某两条边变成出现一遍,这样的话可能会有一些点的度数变成奇数

如果我们把两条非自环的边变成出现一遍,并且这两条边不交于同一个点,那么就会有四个度数为奇数的点,则图中不存在欧拉路径

如果我们把两条非自环的边变成出现一遍,并且这两条边交于同一个点,那么就会有两个度数为奇数的点,存在欧拉路径

如果我们把两条自环边变成出现一遍,所有点的度数仍然为偶数,存在欧拉路径

如果我们把一条自环,一条非自环的边变成出现一遍,那么就会有两个度数为奇数的点,存在欧拉路径

所以一共就几种情况,除去判联通的部分,我们只要记录每个点的度数(不含自环)和自环的数量就好了

因为题目中保证一条边不会出现两遍,所以我们的方法才是可行的

代码:

 #include <bits/stdc++.h>

 using namespace std;
typedef long long ll;
const int MAXN = ; int n, m; namespace Graph {
int head[MAXN], nxt[MAXN<<], to[MAXN<<], eidx;
void init() {
eidx = ;
memset( head, -, sizeof(head) );
}
void adde( int u, int v ) {
to[eidx] = v, nxt[eidx] = head[u], head[u] = eidx++;
}
} bool ing[MAXN] = {}, vis[MAXN] = {}; // ing表示这个点是否存在于图中,因为题目只要求边互相联通,所以对于没有度数的点可以看做不存在
queue<int> q;
bool bfs() { // bfs判联通
using namespace Graph;
for( int i = ; i <= n; ++i )
if( ing[i] ) {
q.push(i), vis[i] = true;
break;
}
while( !q.empty() ) {
int u = q.front(); q.pop();
for( int i = head[u]; ~i; i = nxt[i] ) {
int v = to[i];
if( vis[v] ) continue;
q.push(v), vis[v] = true;
}
}
for( int i = ; i <= n; ++i )
if( ing[i] && !vis[i] )
return false;
return true;
} int deg[MAXN] = {}, loop = ; // 每个点的度数(不含自环)和总的自环数量
int main() {
scanf( "%d%d", &n, &m );
Graph::init();
for( int i = ; i < m; ++i ) {
int u, v; scanf( "%d%d", &u, &v );
ing[u] = ing[v] = true;
if( u != v ) {
Graph::adde(u,v), ++deg[u];
Graph::adde(v,u), ++deg[v];
} else { // 自环
Graph::adde(u,v), ++loop;
}
}
if( !bfs() || m < ) {
puts("");
return ;
}
ll ans = (ll)loop*(m-loop) + (ll)loop*(loop-)/; // 选一个自环和一个非自环,或者选两个自环
for( int i = ; i <= n; ++i )
ans += (ll)deg[i]*(deg[i] - )/; // 选两个非自环,且交于同一点的边
cout << ans << endl;
return ;
}

最新文章

  1. 【ASP.NET程序员福利】打造一款人见人爱的ORM(一)
  2. [React] 多组件生命周期转换关系
  3. GIT 从入门到放弃大整理
  4. String.getBytes()
  5. Neo4j 3.0 存储过程
  6. Cocoapods的安装
  7. 编译原理:正规式转变成DFA算法
  8. html初始化页面和a标签无下划线
  9. iOS集成ijkplayer视频直播框架,遇到的bug和坑...
  10. Linggle: 英语写作学习搜索引擎
  11. JDBC第四次学习
  12. web前端开发常用工具
  13. ubuntu下安装java和eclipse
  14. Missing number in array
  15. 防盗链[referer]
  16. 【二代示波器教程】第15章 FreeRTOS操作系统版本二代示波器实现
  17. centos查看系统/硬件信息及运维常用命令
  18. MySQL表数据的增删改查
  19. 【CSS】小妙招,各种问题总结方法处理
  20. 机器学习基石笔记:08 Noise and Error

热门文章

  1. logisitic回归
  2. 1.EOS源码编译运行
  3. nginx配置和网站的部署
  4. Thunder团队第二周 - Scrum会议2
  5. PHPCMS调取当前栏目的描述、文章位置导航、当前栏目链接、当前栏目名称
  6. lintcode-143-排颜色 II
  7. Qt代码覆盖率code coverage(VS版)
  8. Bootstrap 按钮,图片,辅助类
  9. WPF文件和文件夹的操作
  10. 【EF Core】Entity Framework Core 批处理语句