题解：P11762 [IAMOI R1] 走亲访友

· · 题解

注意到 k \ge n+m。

如果本题给定的图是欧拉图，那么可以在一次旅行中遍历一遍所有的边，也就意味着可以自由决定给定的所有边中保留哪些边。

此时，只需要 dfs 一遍找出一个生成树（此处默认 s 为根），然后删除所有非树边，即可解决本题。

但是给定图并不保证是欧拉图。

但是题目并没有禁止我们多次遍历同一条边，也就是说可以添加不超过 n 条额外的重边。

考虑对于要构建的那个生成树，对其从根开始递归处理，处理完当前节点的子树之后，若当前节点度数是奇数，那么向自己的父节点连一条边使得当前节点度数变为偶数。

但是根节点没有父节点怎么办？注意到若除了根节点以外的所有节点度数都为偶数了，那么根节点度数一定也是偶数，因为一条边对图的总度数贡献是 2，也就是说图的总度数为偶数。

无向图欧拉回路的一个简单的写法，可以考虑 set 维护所有出边，每搜索一个点，就将这条边从两个端点的出边列表删除，时间复杂度 O(m \log m)。 

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
const int maxn=1e3+5;
int n,m,k,s;
vector<pii> g[maxn];
multiset<pii> g2[maxn]; 
bool ontree[maxn*maxn];
int deg[maxn];
bool vis[maxn];
void dfs1(int u,int _fa,int ine){
    vis[u]=1;
    for(auto& tmp:g[u]){
        if(!vis[tmp.fi]){
            ontree[tmp.se]=1;
            dfs1(tmp.fi,u,tmp.se);
        }
    }
    if(deg[u]&1)g2[u].insert(mkpr(_fa,ine)),g2[_fa].insert(mkpr(u,ine)),deg[u]++,deg[_fa]++;
}
stack<pii> ans;
int cur[maxn];
void dfs2(int u){
    while(!g2[u].empty()){
        auto tmp=*g2[u].begin();
        g2[u].erase(g2[u].begin());
        g2[tmp.fi].erase(g2[tmp.fi].find(mkpr(u,tmp.se)));
        dfs2(tmp.fi);
        ans.push(mkpr(tmp.se,ontree[tmp.se]));
    }
}
void solve(int id_of_test){
    read(n);
    read(m);
    read(k);
    read(s);
    FOR(i,1,m){
        int u,v;
        read(u);
        read(v);
        g[u].eb(mkpr(v,i));
        g[v].eb(mkpr(u,i));
        deg[u]++,deg[v]++;
    }
    FOR(u,1,n){
        for(auto& tmp:g[u])g2[u].insert(tmp);
    }
    dfs1(s,0,0);
    dfs2(s);
    printf("%d\n",int(ans.size()));
    while(!ans.empty()){
        printf("%d %d\n",ans.top().fi,ans.top().se);
        ans.pop(); 
    }
}
int main()
{
    int T;
    T=1;
    FOR(_,1,T){
        solve(_);
    }
    return 0;
}