2024 ICPC ShaanXi Provincial Contest —— C. Seats（个人理解）拓扑+dfs

先放个传送门
https://codeforces.com/gym/105257/problem/C

————————————————————————————————————

思路

可以看到，每一个编号可能会被很多人向往，但每一个编号上的人只会向往一个座位。

再有可以发现，如果根据每个人的期望建边之后成环了，那么这个环内所有人都可以实现向往，但任何一条链从环出发或者终点到环的情况是都不可能实现的。环只能自给自足，而与环相接的链上的人必然不可能实现向往！

那么排除上面必死的链之外，还有什么链是可以实现的？不难发现，如果终点在 n+1 到 2*n 的链是都可以实现的。并且这些链之间是不会互相干扰的。

那么我们的目标就变成了：

①统计所有环的节点数

②统计终点在右半边的所有最长链长度和

详细步骤请看代码实现：

#include<bits/stdc++.h>
#include<assert.h>
using namespace std;
typedef long long ll;const ll M = 2e5 + 20;
const ll inf = 1e9 + 5;
const ll P = 1e9 + 7;//vector<int>g[M];
vector<int>gb[M];//反向建边ll n;
ll a[M];bitset<M>loop;//1表示属于环，0不属于
ll in[M];//每个节点的入度
ll ans = 0;//dfs从终点反着找最长链
int dfs(int x)
{if (loop[x])//环只能自给自足return 0;int maxx = 0;for (auto& y : gb[x])maxx = max(maxx, dfs(y));return maxx + 1;
}void topo()
{queue<int>q;for (int i = 1; i <= n; i++)if (in[i] == 0)q.push(i);while (!q.empty()){int ttt = q.front();q.pop();loop[ttt] = 0;//入度为0说明肯定不是环if (a[ttt] > n)//到右半边的不用管continue;if (--in[a[ttt]] == 0)//产生的新的入度为0的点加入队列q.push(a[ttt]);}
}void solve()
{cin >> n;//先进行录入for (int i = 1; i <= n; i++){cin >> a[i];gb[a[i]].push_back(i);//反向建边in[a[i]]++;//处理入度}for (int i = 1; i <= n; i++)loop[i] = 1;//拓扑排序来排除环以外的点topo();//在环里的每个人都可以互相交换for (int i = 1; i <= n; i++)if (loop[i])ans++;//反着找以 n+1 到 n 为终点的最长链for (int i = n + 1; i <= 2 * n; i++)ans += dfs(i) - 1;//减去多余的一个cout << ans << '\n';
}int main()
{std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//cout << fixed << setprecision(4);int T = 1;//cin >> T;while (T--)solve();return 0;
}