Euler-path
2024-10-07 00:41:35
对于每个连通块欧拉回路存在的条件
无向图:只存在两个或者零个度数为奇数的点
有向图:每个点的入度等于出度或者至多有两个点入度不等于出度且一个出度比入度多一另一个入度比出度多一
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 ;
}
最新文章
- jquery.ajax
- WPF内置命令
- Git命令行(转用于学习和记录)
- beaglebone_black_学习笔记&mdash;&mdash;(9)UART使用
- 6.nodejs权威指南--进程
- Ruby界面开发--wxRuby库TextCtrl相关问题
- bzoj2428: [HAOI2006]均分数据
- C++ Brush
- cobbler常见问题
- mongoDB初接触
- qml demo分析(externaldraganddrop-拖拽)
- 同步IO,异步IO,阻塞IO,非阻塞IO
- 福州大学软件工程1916|W班 第3次作业成绩排名
- 配置Spark
- C# [Win32] [GDI+] [API] Load HFONT from Memory
- CodeForces12D 树状数组降维
- v-for
- HashMap与TreeMap按照key和value排序
- 20.多线程.join()和setDaemon()的使用
- python 求3到8位数的水仙花数Pycharm实现