中南多校对抗赛 第三场 E

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 ;

}

```