给定一张图，请你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。
输入格式
第一行包含一个整数t, t∈ {1,2}，如果t =1，表示所给图为无向图，如果t=2，表示所给图为有向图。
第二行包含两个整数n, m，表示图的结点数和边数。
接下来m行中，第i行两个整数v, ui，表示第i条边(从1开始编号)。
。如果t一1则表示 v到ug有一条无向边。
。如果t=2则表示 vg到ui有一条有向边。
图中可能有重边也可能有自环。
点的编号从1到n。
输出格式
如果无法—笔画出欧拉回路，则输出一行:NO。
否则，输出一行:YES，接下来一行输出任意一组合法方案即可。
。如果t =1，输出m个整数p,p2,.. .,pm。令e =lp:|，那么e表示经过的第i条边的编号。如果p为正数表示从ve走到ue，否则表示从ue走到ve。
。如果t =2，输出m个整数p1,P2,. . . ,Pm。其中p表示经过的第i条边的编号。
数据范围
1≤n≤105,0 ≤m≤2×105

输入样例1：

1
3 3
1 2
2 3
1 3

输出样例1：

YES
1 2 -3

输入样例2：

2
5 6
2 3
2 5
3 4
1 2
4 2
5 1

输出样例2：

YES
4 1 3 5 2 6

题解:

 根据题中所说,如果边为无向,度数为奇数的点只能有0个,

如果变为有向,所有出均等于入度

接着我们就根据模板找到欧拉回路即可

由于图可能不连通,所有如果有边没联通也要判断

#include 
#include 
#include 
#include using namespace std;const int N = 100010, M = 400010;int type;
int n, m;
int h[N], e[M], ne[M], idx;
bool used[M];
int ans[M], cnt;
int din[N], dout[N];void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}void dfs(int u)
{for (int &i = h[u]; ~i;)//遍历的是当前的边,由于&的存在,优化{if (used[i])//记录走过的路,不会再走{i = ne[i];continue;}used[i] = true;if (type == 1) used[i ^ 1] = true;如果是无向图,反向边也要当作走过int t;if (type == 1){t = i / 2 + 1;if (i & 1) t = -t;}else t = i + 1;//由于边的编号均从0开始,所以无向图,有向图都要+1int j = e[i];i = ne[i];dfs(j);ans[ ++ cnt] = t;}
}int main()
{scanf("%d", &type);scanf("%d%d", &n, &m);memset(h, -1, sizeof h);for (int i = 0; i < m; i ++ ){int a, b;scanf("%d%d", &a, &b);add(a, b);if (type == 1) add(b, a);din[b] ++ , dout[a] ++ ;}if (type == 1){for (int i = 1; i <= n; i ++ )if (din[i] + dout[i] & 1){puts("NO");return 0;}}else{for (int i = 1; i <= n; i ++ )if (din[i] != dout[i]){puts("NO");return 0;}}for (int i = 1; i <= n; i ++ )if (h[i] != -1){dfs(i);break;}if (cnt < m){puts("NO");return 0;}puts("YES");for (int i = cnt; i; i -- ) printf("%d ", ans[i]);puts("");return 0;
}