Codeforces Round #375 (Div. 2) E. One-Way Reform

发表于 更新于 分类于

链接

https://codeforces.com/contest/723/problem/E

题意

将无向图转为有向图，使图中入度等于出度的点尽量多。

思路

无向图中度数为奇数的点必定有偶数个。

因此我们建立一个虚点与度数为奇数的点相连，这样图中就没有度数为奇数的点了，所以图中所有连通图都存在欧拉回路。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
//head
const int N=205;
int n,m,cnt,head[N],to[N*N],nxt[N*N],d[N],in[N],out[N];
bool st[N*N],f[N];
VPII res;
void add_edge(int u,int v) {
    nxt[++cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt;
}
void init() {
    for(int i=1;i<=n+1;i++) head[i]=0,f[i]=false;
    for(int i=1;i<=n;i++) d[i]=in[i]=out[i]=0;
    for(int i=2;i<=cnt;i++) st[i]=0;
    cnt=1;
    res.clear();
}
void hierholzer(int s) {
    stack<int> stk;
    stk.push(s);
    while(SZ(stk)) {
        int u=stk.top(),i=head[u];
        while(i&&st[i]) i=nxt[i];
        if(i) {
            stk.push(to[i]);
            st[i]=st[i^1]=true;
            f[to[i]]=f[to[i^1]]=true;
            if(to[i^1]!=n+1&&to[i]!=n+1) res.EB(to[i],to[i^1]);
            head[u]=nxt[i];
        }
        else stk.pop();
    }
}
int main() {
    //freopen("E:/OneDrive/IO/in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin>>T;
    while(T--) {
        init();
        cin>>n>>m;
        for(int i=1;i<=m;i++) {
            int u,v;
            cin>>u>>v;
            add_edge(u,v);
            add_edge(v,u);
            ++d[u],++d[v];
        }
        int tot=0;
        for(int i=1;i<=n;i++) if(d[i]&1) ++tot,add_edge(i,n+1),add_edge(n+1,i);
        for(int i=1;i<=n+1;i++) if(!f[i]) hierholzer(i);
        cout<<n-tot<<'\n';
        for(auto x:res) cout<<x.FI<<' '<<x.SE<<'\n';
    }
    return 0;
}