Problem – E – Codeforces

思路

我们意识到不同伙伴恰如一个边，人就是点，一个圆圈舞中，每个人的度都是2
所以我们可以分成两类

• 闭环：每个点都有两个边，这样就不能接入其他点，必须作为独立的圆圈舞
• 开链：链的两端度数均为1，仍有一个空闲度数可供连接

我们统计闭环数为$cycle$，开链数为$path$

• 最大数量：$mx=cycle+path$，我们将$path$首尾相连
• 最小数量：$mi=cycle+(path > 1 ? 1 ： 0)$如果有$path$那么我们就首尾相连，最终只有一个，没有$path$就更好了

代码

//Sunshine sunshine ladybugs awake,

//Clap your hooves and do a little shack.

#include<bits/stdc++.h>

using namespace std;

  

using PII=pair<int,int>;

  

void solve(){

    int n;

    cin>>n;

  

    vector<PII> edges;

    for(int u=1;u<=n;u++){

        int v;

        cin>>v;

        edges.push_back({min(u,v),max(u,v)});

    }

  

    sort(edges.begin(),edges.end());

    edges.erase(unique(edges.begin(),edges.end()),edges.end());

  

    vector<vector<int>> g(n+1);

    for(auto [u,v]:edges){

        g[u].push_back(v);

        g[v].push_back(u);

    }

  

    vector<bool> vis(n+1,false);

    int cycle=0,path=0;

  

    for(int i=1;i<=n;i++){

        if(!vis[i]){

            int point=0;

            int degree=0;

  

            queue<int> q;

            q.push(i);

            vis[i]=true;

  

            while(!q.empty()){

                int u=q.front();

                q.pop();

                point++;

                degree+=g[u].size();

  

                for(auto v:g[u]){

                    if(!vis[v]){

                        vis[v]=true;

                        q.push(v);

                    }

                }

            }

  

            int edges=degree/2;

            if(point==edges){

                cycle++;

            }else{

                path++;

            }

        }

    }

  

    int mi=cycle+(path>0?1:0);

    int mx=cycle+path;

  

    cout<<mi<<" "<<mx<<endl;

}

  

signed main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int t;cin>>t;while(t--)

    solve();

    return 0;

}