对于每个连通块欧拉回路存在的条件

无向图:只存在两个或者零个度数为奇数的点

有向图:每个点的入度等于出度或者至多有两个点入度不等于出度且一个出度比入度多一另一个入度比出度多一

HDU 多校第二场 C.cover

题意:给你一个无向图 问你一笔画最多多少次能把所有边覆盖(走过的边不能走)

并且输出每个一笔画的路径(边的下标)

解:给每一对度数为奇数的点连上一条边使之度数变成偶数 然后跑欧拉回路

欧拉回路是从一个正确的点出发然后暴力dfs遇到走过的边就不要走

/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + , gakki = + + + + 1e9;
const int MAXN = 1e5 + , MAXM = 2e5 + , MAXQ = , INF = 1e9;
const ll LLINF = (1LL << );
int to[MAXM << ], nxt[MAXM << ], Head[MAXN], tot = ;
int index[MAXM << ];
bool used[MAXM << ];
inline void addedge(int u, int v, int x)
{
if (u == v)
{
return ;
}
to[++tot] = v;
nxt[tot] = Head[u];
index[tot] = x;
used[tot] = false;
Head[u] = tot;
}
inline void read(int &v)
{
v = ;
char c = ;
int p = ;
while (c < '' || c > '')
{
if (c == '-')
{
p = -;
}
c = getchar();
}
while (c >= '' && c <= '')
{
v = (v << ) + (v << ) + c - '';
c = getchar();
}
v *= p;
}
int n, m;
int du[];
bool visit[];
int ans = ;
vector<int> anser[];
int cnt = ;
void dfs(int x)
{
int nowindex;
visit[x] = true;
for (int v, i = Head[x]; i; i = nxt[i])
{
v = to[i];
if (used[i])
{
continue;
}
used[i] = used[i ^ ] = true;
nowindex = index[i];
//cout << x << " to " << v << " index " << nowindex << " i " << i << endl;
dfs(v);
if (nowindex == )
{
anser[++cnt].clear();
}
else
{
anser[cnt].push_back(-nowindex);
}
}
}
int main()
{
ios_base::sync_with_stdio();
cin.tie(); int u, v;
while (~scanf("%d %d", &n, &m))
{
cnt = ;
tot = ;
for (int i = ; i <= n; i++)
{
du[i] = ;
visit[i] = false;
Head[i] = ;
}
for (int i = ; i <= m; i++)
{
read(u), read(v);
addedge(u, v, i);
addedge(v, u, -i);
du[u]++, du[v]++;
}
int aim = ;
for (int i = ; i <= n; i++)
{
if (du[i] & )
{
if (aim)
{
addedge(aim, i, );
addedge(i, aim, );
aim = ;
}
else
{
aim = i;
}
}
}
for (int i = ; i <= n; i++)
{
if (!visit[i] && (du[i] & ))
{
anser[++cnt].clear();
dfs(i);
cnt--;
}
}
for (int i = ; i <= n; i++)
{
if (!visit[i] && du[i])
{
anser[++cnt].clear();
dfs(i);
}
}
printf("%d\n", cnt);
for (int i = ; i <= cnt; i++)
{
printf("%d ", anser[i].size());
for (int j = ; j < anser[i].size(); j++)
{
printf("%d", anser[i][j]);
if (j == anser[i].size() - )
{
putchar('\n');
}
else
{
putchar(' ');
}
}
}
}
return ;
}

最新文章

  1. jquery.ajax
  2. WPF内置命令
  3. Git命令行(转用于学习和记录)
  4. beaglebone_black_学习笔记&mdash;&mdash;(9)UART使用
  5. 6.nodejs权威指南--进程
  6. Ruby界面开发--wxRuby库TextCtrl相关问题
  7. bzoj2428: [HAOI2006]均分数据
  8. C++ Brush
  9. cobbler常见问题
  10. mongoDB初接触
  11. qml demo分析(externaldraganddrop-拖拽)
  12. 同步IO,异步IO,阻塞IO,非阻塞IO
  13. 福州大学软件工程1916|W班 第3次作业成绩排名
  14. 配置Spark
  15. C# [Win32] [GDI+] [API] Load HFONT from Memory
  16. CodeForces12D 树状数组降维
  17. v-for
  18. HashMap与TreeMap按照key和value排序
  19. 20.多线程.join()和setDaemon()的使用
  20. python 求3到8位数的水仙花数Pycharm实现

热门文章

  1. HBase 数据恢复
  2. app测试自动化之混合APP(之前的三篇为原生APP的操作)
  3. Linux手册页惯用的节名
  4. 如何为根分区扩容(centos7为例)
  5. JS延迟加载的几种方式
  6. 简洁易懂说VLAN
  7. sqlalchemy orm的cascade的参数
  8. Rsyslog收集应用日志
  9. Java 虚拟机的运行模式
  10. (5.12)mysql高可用系列——复制中的在线切换GTID模式/增加节点/删除节点