E:Eulerian Flight Tour

题意:

给你一张无向图,要你给这个图加边使得其形成一个欧拉回路

题解:

首先使得所有节点的度都为偶数,然后将这个图联通起来

对于度为奇数的点,将将他和他的父节点连接起来

连接完后如果这个图是联通的,那么就直接输出结果

如果这个图有多个联通块:

分类讨论:

如果有2个联通块,两个联通块对着连成一个环

如果有多个联通块,用一个环将这几个联通块连起来即可

代码:

# E:Eulerian Flight Tour

## 题意:

给你一张无向图,要你给这个图加边使得其形成一个欧拉回路

## 题解:

首先使得所有节点的度都为偶数,然后将这个图联通起来

对于度为奇数的点,将将他和他的父节点连接起来

连接完后如果这个图是联通的,那么就直接输出结果

如果这个图有多个联通块:

分类讨论:

如果有2个联通块,两个联通块对着连成一个环

如果有多个联通块,用一个环将这几个联通块连起来即可

代码:

```c++
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define FIN freopen("input.txt","r",stdin);
const int maxn = 4e3 + ;
int n, m;
int vis[maxn];
int deg[maxn];
bool G[maxn][maxn];
bool flag;
vector<pii> ans;
void dfs(int u, int p) {
vis[u] = ;
for(int v = ; v <=n; v++) {
if(vis[v]) continue;
if(G[u][v]) continue;
dfs(v, u);
}
if(deg[u] & ) {
if(p == -) flag = false;
else {
ans.push_back(make_pair(u, p));
deg[u]++, deg[p]++;
G[u][p] = G[p][u] = ;
}
}
} vector<int> tmp;
vector<vector<int>> A;
void dfs1(int u) {
vis[u] = ;
for(int v = ; v <= n; v++) {
if(v == u) continue;
if(vis[v]) continue;
if(!G[u][v]) continue;
dfs1(v);
}
tmp.push_back(u);
}
int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
cin >> n >> m;
memset(deg,,sizeof(deg));
memset(G,,sizeof(G));
for(int i = , u, v; i < m; i++) {
cin >> u >> v;
// u--,v--;
deg[u]++, deg[v]++;
G[u][v] = G[v][u] = ;
}
// cout<<"hhh"<<endl;
flag = true;
ans.clear();
for(int i = ; i <= n; i++) {
if(vis[i]) continue;
dfs(i, -);
}
if(!flag) {
cout << - << endl;
} else {
memset(vis, , sizeof(vis));
for(int i = ; i <= n; i++) {
if(vis[i]) continue;
tmp.clear();
dfs1(i);
A.push_back(tmp);
}
if (A.size() == ) {
if (A[].size() > A[].size()) swap(A[], A[]);
if (A[].size() == ) {
int t = A[][];
int u = -, v=-;
for (int i = ; i < A[].size(); ++i) {
for(int j = i + ; j < A[].size(); ++j) {
int cu = A[][i], cv = A[][j];
if (!G[cu][cv]) u = cu, v = cv;
}
}
if (u == -) {
if (ans.size() == ) {
cout << - << endl;
return ;
}
u = ans.back().first;
v = ans.back().second;
ans.pop_back();
} else {
ans.push_back(make_pair(u, v));
}
ans.push_back(make_pair(t, u));
ans.push_back(make_pair(t, v));
} else {
for (int it = ; it < ; ++it) {
for (int it2 = ; it2 < ; ++it2) {
ans.push_back(make_pair(A[][it], A[][it2]));
}
}
}
} else if (A.size() > ) {
for (int i = ; i < A.size(); ++i) {
int j = (i + ) % A.size();
ans.push_back(make_pair(A[i][], A[j][]));
}
}
cout << ans.size() << endl;
for (int i = ; i < ans.size(); i++) {
if (ans[i].first > ans[i].second) swap(ans[i].first, ans[i].second);
cout << ans[i].first << " " << ans[i].second << endl;
}
}
return ;
} ```
05-11 09:41