P10693 [SNCPC2024] 换座位

本题考虑建图转化为图论问题，把每个嘉宾向其心仪座位连边，样例如下。

不难发现编号小于等于 \(n\) 的点出度一定为 \(1\)，当一个联通块内全是编号小于等于 \(n\) 时，这个联通块有 \(n\) 条边；否则有 \(n-1\) 条边。因此这张图一定是一个有向基环树和有向树构成的森林。

对于有向树，我们遍历所有大于 \(n\) 小于等于 \(2n\) 的点，求出树上最长链边数，由于编号大于 \(n\) 的点出度为 \(0\)，所以我们考虑建一张反图，方便 dfs 求解。

对于有向基环树，只能是环上的所有点，不然存在嘉宾没有地方坐，找环可以使用拓扑排序。

代码（参考了洛谷题解）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+10;
vector<int>g1[MAXN],g2[MAXN];//图和反图
bool vis[MAXN];//标记
int ind[MAXN];//入度
int a[MAXN];
int n;
int maxn=0;
void dfs(int u,int fa,int now){
    if(u<=n){
        maxn=max(maxn,now);
        vis[u]=true;
        //不应return
    }
    for(auto v:g2[u]){
        if(v==fa)continue;
        dfs(v,u,now+1);
    }
}
int ans=0;
signed main(){
    cin>>n;
    for(int i=1;i<=2*n;i++){
        cin>>a[i];
        g1[i].push_back(a[i]);
        g2[a[i]].push_back(i);
        ind[a[i]]++;
    }
    for(int i=n+1;i<=2*n;i++){//计算有向树
        maxn=0;
        dfs(i,0,0);
        ans+=maxn;
    }
    queue<int>q;
    for(int i=1;i<=n;i++){
        if(ind[i]||vis[i])continue;
        q.push(i);
    }
    while(q.size()){//拓扑排序
        int u=q.front();
        q.pop();
        vis[u]=true;
        for(auto v:g1[u]){
            ind[v]--;
            if(!ind[v])q.push(v);
        }
    }
    for(int i=1;i<=n;i++)//找环
        if(!vis[i])ans++;
    cout<<ans;
    return 0;
}