如果边数为奇数，一定无解。
如果边数为偶数，一定有解。考虑证明：
我们可以先随便定向，然后给每个点 \(i\) 一个值 \(a_i\in\{0,1\}\)，表示出边条数奇偶性。
然后随便考虑图的一颗生成树。
注意到一条边 \((u,v)\) 翻转定向会让 \(a_u\gets 1-a_u,a_v\gets 1-a_v\)。
这等于把 \(1\) 从边的一段移动到另一端，碰上了就消掉。
有很多这种套路的，比如
通过贪心满足孩子节点，一定可以构造出一种边定向的方案。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, M = 2e5 + 5;
int m, n;
int deg[N];
bool ch[M], vis[N];
vector<pair<int, int>> e[N];
void dfs(int x, int fa)
{
vis[x] = 1;
for(auto [i, id] : e[x])
{
if(vis[i]) continue;
dfs(i, x);
if(deg[i])
{
deg[x] ^= 1;
ch[id] = 0;
}
}
}
int u[M], v[M];
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i ++)
{
int x, y; cin >> x >> y;
ch[i] = 1;
u[i] = x, v[i] = y;
e[x].push_back({y, i});
e[y].push_back({x, i});
deg[x] ^= 1;
}
dfs(1, 0);
if(deg[1]) return cout << -1, 0;
for(int i = 1; i <= m; i ++)
if(ch[i]) cout << u[i] << " " << v[i] << "\n";
else cout << v[i] << " " << u[i] << "\n";
return 0;
}
构造生成树可以用并查集，也可以直接 dfs 搜。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, M = 2e5 + 5;
int m, n;
int fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
int deg[N];
bool ch[M];
vector<pair<int, int>> e[N];
void dfs(int x, int fa)
{
for(auto [i, id] : e[x])
{
if(i == fa) continue;
dfs(i, x);
if(deg[i])
{
deg[x] ^= 1;
ch[id] = 0;
}
}
}
int u[M], v[M];
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i ++) fa[i] = i;
for(int i = 1; i <= m; i ++)
{
int x, y; cin >> x >> y;
u[i] = x, v[i] = y;
ch[i] = 1;
deg[x] ^= 1;
if(find(x) == find(y)) continue;
e[x].push_back({y, i});
e[y].push_back({x, i});
fa[find(x)] = find(y);
}
dfs(1, 0);
if(deg[1]) return cout << -1, 0;
for(int i = 1; i <= m; i ++)
if(ch[i]) cout << u[i] << " " << v[i] << "\n";
else cout << v[i] << " " << u[i] << "\n";
return 0;
}