# 杭电多校2018第二场 HDU6311 Cover（欧拉路径）

## Cover

• Time Limit: 6000/3000 MS (Java/Others)
• Memory Limit: 32768/32768 K (Java/Others)
• Total Submission(s): 1640
• Accepted Submission(s): 349Special Judge

### Problem Description

The Wall has down and the King in the north has to send his soldiers to sentinel.
The North can be regard as a undirected graph (not necessary to be connected), one soldier can cover one path. Today there's no so many people still breathing in the north, so the King wants to minimize the number of soldiers he sent to cover each edge exactly once. As a master of his, you should tell him how to arrange soldiers.

### Input

There might be multiple test cases, no more than 20. You need to read till the end of input.
In the first line, two integers n and m, representing the number of nodes and edges in the graph.
In the following m lines, each contain two integers, representing two ends of an edge.
There are no parallel edges or self loops.
1≤n,m≤100000

### Output

For each test case, the first line contains number of needed routes, p.
For the following p lines, an integer x in the beginning, followed by x integers, representing the list of used edges. Every integer should be a positive or negative integer. Its absolute value represents the number of chosen edge (1~n). If it's positive, it shows that this edge should be passed as the direction as the input, otherwise this edge should be passed in the direction different from the input. Edges should be in correct order.

### Sample Input

3 3
1 2
1 3
2 3

### Sample Output

1
3 1 3 -2

### Source

2018 Multi-University Training Contest 2

### 链接

http://acm.hdu.edu.cn/showproblem.php?pid=6311

### 代码

StatusAccepted
Time1154ms
Memory11124kB
Length2196
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100010;
int tot, cnt, n, m;
struct Edge
{
int to, next, id;
bool f;
}edge[maxn<<2]; // NO MLE
bool vis[maxn];
vector <int> V[maxn];
int degree[maxn];

void init()
{
cnt = tot = 0;
for (int i = 0; i <= n; ++i)
{
degree[i] = 0;
vis[i] = false;
}
//  memset(edge, 0, sizeof(edge)); // MLE
}

void addedge(int u, int v, int id) // 链式前向星存边
{
edge[tot].to = v;
edge[tot].id = id;
edge[tot].f = false;
}

void dfs(int u)
{
vis[u] = true;
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
int id = edge[i].id;
if (!edge[i].f)
{
edge[i].f = edge[i^1].f = true; // 标记边和反向边
dfs(v);
if (id) // 实边
V[cnt].push_back(-id); // 退栈过程中记录边的id，为负是因为先访问方向边
else // 遇到虚边，路径加1
cnt++;
}
}
}

void Print()
{
printf("%d\n", cnt);
for (int i = 0; i < cnt; ++i)
{
int len = V[i].size();
printf("%d", len);
for (int j = 0; j < len; j++)
printf(" %d", V[i][j]);
printf("\n");
V[i].clear();
}
}

int main()
{
int u, v;
while (scanf("%d%d", &n, &m) == 2)
{
init();
for (int i = 1; i <= m; ++i)
{
scanf("%d%d", &u, &v);
degree[u]++, degree[v]++;
}
int pos = 0;
for (int i = 1; i <= n; ++i)
{
if (degree[i] & 1) // 度数为奇数的点连边
{
if (pos > 0)
{
pos = 0;
}
else
pos = i;
}
}
for (int i = 1; i <= n; ++i) // 度数为奇数
{
if (!vis[i] && (degree[i]&1))
dfs(i);
}
for (int i = 1; i <= n; ++i)
{
if (!vis[i] && degree[i])
{
dfs(i);
cnt++;
}
}
Print();
}
return 0;
}

The end.
2018-07-28 星期六