欧拉通路与欧拉回路
欧拉通路:对于图G来说,如果存在一条通路包含G中所有的边,则该通路成为欧拉通路,也称欧拉路径。
欧拉回路:如果欧拉路径是一条回路,那么称其为欧拉回路。
欧拉图:含有欧拉回路的图是欧拉图。
对无向图G和有向图H:
图G存在欧拉路径与欧拉回路的充要条件分别是:
欧拉路径:图中所有奇度点的数量为0或2。
欧拉回路:图中所有点的度数都是偶数。
图H存在欧拉路径和欧拉回路的充要条件分别是:
欧拉路径:所有点的入度等于出度 或者 存在一点出度比入度大1(起点),一点入度比出度大1(终点),其他点的入度均等于出度。
欧拉回路:所有点的入度等于出度。
O(m)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<int, string> PIS;
typedef pair<double, double> PDD;
const double eps = 1e-6;
const int N = 1e5 + 10, M = 4*N, P = 1e9 + 7, INF = 0x3f3f3f3f;
int n, m;
int type;
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] = 1;
if (type == 1)
{
used[i ^ 1] = 1;
}
int t;
if (type == 1)
{
t = i / 2 + 1;
if (i & 1)
{
t = -t;
}
}
else
{
t = i + 1;
}
int v = e[i];
i = ne[i];
dfs(v);
ans[++cnt] = t;
}
}
int main()
{
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
cin >> type;//type1为无向图,2为有向图
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i++)
{
int a, b;
cin >> 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)
{
cout << "NO" << endl;
return 0;
}
}
}
else
{
for (int i = 1; i <= n; i++)
{
if (din[i] != dout[i])
{
cout << "NO" << endl;
return 0;
}
}
}
for (int i = 1; i <= n; i++)
{
if (h[i] != -1)
{
dfs(i);
break;
}
}
if (cnt < m)
{
cout << "NO" << endl;
return 0;
}
cout << "YES" << endl;
for (int i = cnt; i; i--)
{
cout << ans[i] << ' ';
}
return 0;
}