P4790

简要题意：给定内向基环树森林，一次操作可以改变一条边的终点，求最小操作次数或判断无解。

无解的话显然就是当且仅当点数是奇数，不然就算是两两暴力配对也一定能出解。

容易发现题目可以转化成一个相邻点配对的问题，最终答案就是配出的对数加上没配上的点数（因为相邻点配对就只用改一条边，没匹配上就最后一起改，一对就要改两条边了）。

然后考虑每一棵基环树，容易注意到环以下的树的部分直接从叶子向上贪心的选一定是不劣的。具体来说，如果一个点和他的父亲都是空余，那么我就算这里无脑选掉最坏情况下也就只会导致父亲和他的父亲没法匹配，额外多出 $1$ 的代价，但是反正我不选也有 $1$ 的代价，那么直接贪心选肯定就是对的。

因此先把树的部分贪心的选完，根据选出的结果，环的部分可能会被分割成若干条线段或者仍然是一个环，但是实际上没有区别，对于每一个连通块大小的奇偶性分别贡献到配对数和散点数里面就行了。

需要特判仍然是环且环长为 $2$ 的情况，因为不需要任何修改。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n;
map<string,int>mp;
int cnt;
int to[N];
vector<int>nbr[N];
int siz[N];
bool vis[N],tag[N];
bool f[N];
int res,res2;
void dfs(int cur){
    siz[cur]=1;
    int cnt=0;
    for(auto to:nbr[cur]){
        if(vis[to])continue;
        dfs(to);
        siz[cur]+=siz[to];
        if(!f[to])cnt++;
    }
    if(cnt>1){
        res2+=cnt-1;
        f[cur]=1;
        res++;
    }
    else if(cnt==0)f[cur]=0;
    else f[cur]=1,res++;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    if(n&1){
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;++i){
        string a,b;
        cin>>a>>b;
        if(!mp[a])mp[a]=++cnt;
        if(!mp[b])mp[b]=++cnt;
        to[mp[a]]=mp[b];
        nbr[mp[b]].push_back(mp[a]);
    }
    for(int i=1;i<=n;++i){
        if(!siz[i]){
            int now=i,tmp=0;
            deque<int>vec;
            while(!tag[now]){
                tag[now]=1;
                now=to[now];
            }
            int o=now;
            vec.push_back(now);
            now=to[now];
            while(now!=o){
                vec.push_back(now);
                now=to[now];
            }
            for(auto x:vec)vis[x]=1;
            bool flg=0;
            for(auto x:vec){
                dfs(x);
                tmp+=siz[x];
                flg|=f[x];
            }
            while(flg&&!f[vec.front()]){
                vec.push_back(vec.front());
                vec.pop_front();
            }
            if(vec.size()!=2){
                int len=0;
                for(auto x:vec){
                    if(f[x]==1){
                        res+=len/2;
                        res2+=len%2;
                        len=0;
                    }
                    else len++;
                }
                res+=len/2;
                res2+=len%2;
            }
        }
    }
    // cout<<res<<' '<<res2<<'\n';
    cout<<res+res2;
    return 0;
}