题意：有最少用多少条边不重复的路径可以覆盖一个张无向图 ，输出每条路径的边的序号 ， 如果是反向就输出-id。
也就是可以多少次一笔画的方式画完这个无向图。
题解：我们已知最优胜的情况是整个图是欧拉图的时候 ，我们只需要一笔就搞定了 ， 可是现在这个图并不是一个欧拉图， 所以现在问题是其转化为欧拉图 ，那我们根据欧拉图的性质 ， 如果一个无向图是欧拉图的时候当且这个图有奇数的度的点有0个或者是2个 ， 而且如果是两个的话那这两个点肯定是起点或者终点 ; 所以现在我们就遍历整个图的奇数点将其连接成为一个欧拉图 ， 然后跑一遍求欧拉路径的算法 ，如果遇到的是我们构造出的虚拟边 ， 是不是就是意味着这里是一个断点 ，需要我们重新起笔在画；
#include<cstdio> #include<vector> #include<algorithm> #include<cstring> #include<iostream> using namespace std; typedef long long ll ; const int maxn = 1e5+5; struct Edge { int to,id,next; bool f; }edges[maxn<<4]; int fa=0; int tot , head[maxn] , cnt; bool vis[maxn]; vector<int> res[maxn]; int deg[maxn]; void init() { tot = 0; cnt = 0; memset(deg,0,sizeof(deg)); memset(vis,0,sizeof(vis)); memset(head,-1,sizeof(head)); } void AddEdge(int u , int v , int id) { edges[tot].f=0; edges[tot].to = v ; edges[tot].id=id; edges[tot].next = head[u] ; head[u] = tot++; } void dfs(int u) { vis[u]=true; for(int i=head[u] ; ~i ; i=edges[i].next) { int v=edges[i].to , id =edges[i].id; if(!edges[i].f) { edges[i].f = edges[i^1].f=true; //将边和反向边标记 dfs(v); if(id) res[cnt].push_back(-id); ///退丈记录边id else cnt++; ///扫到虚边，那么路径加1 } } } void Print() { printf("%d ",cnt); for(int i=1 ; i<=cnt ; i++) { printf("%d",res[i].size()); for(int j=0 ; j<res[i].size() ; ++j) printf(" %d",res[i][j]); puts(""); res[i].clear(); } } int main() { int T,N,M,u,v,tmp; while(~scanf("%d%d",&N,&M)) { init(); for(int i=1 ; i<=M ; i++) { scanf("%d%d",&u,&v); deg[u]++ , deg[v]++; AddEdge(u,v,i); AddEdge(v,u,-i); } ///将图的奇数的度连起 u=0; for(int i=1 ; i<=N ; i++) { if(deg[i]&1) { if(u) { AddEdge(u,i,0); AddEdge(i,u,0); u=0; } else u=i; } } for(int i=1 ; i<=N ; i++) { if(!vis[i] && (deg[i]&1)) { cnt++; ///细节处理cnt ， 如果出现虚边cnt++ , 下次dfs()还cnt++ , 这是不对的 dfs(i); cnt--; } } for(int i=1 ; i<=N ; i++) { if(!vis[i] && deg[i]) { cnt++; ///偶数的点不会出现虚遍 dfs(i); } } Print(); } return 0; }