题目
D - Equals
给出\(1\sim n\)的排列p，给出\(m\)种对换\((p_i, p_j)\)，在这\(m\)种对换中任选操作，对原排列对换任意多次。求能够实现的\(p_i = i\)的最大个数为多少？
思路
- 将m中对换中能够相互关联的位置归为一组，这组位置之间可通过对换操作实现任意顺序；
- 因而对于一组内的数据，是需要求出组中涉及的原始位置集合\(\{i\}\)与原始排列数集合\(\{p_i\}\)的交集，将所有组求得的交集元素个数相加即为答案。
- 具体方法：使用并查集结组；使用set处理集合求交。
总结
- 意识到“组内位置之间可通过对换操作实现任意顺序”是关键。
代码
点击查看代码
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
using LL = long long;
const int N = 1e5 + 10;
int p[N];
set<int> st[N];
int fa[N];
int find(int x)
{
if (fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
void solv()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++) fa[i] = i;
for (int i = 1; i <= n; i ++) cin >> p[i];
for (int i = 1; i <= m; i ++)
{
int x, y;
cin >> x >> y;
x = find(x);
y = find(y);
fa[y] = x;
}
for (int i = 1; i <= n; i ++)
{
int t = find(i);
st[t].insert(p[i]);
}
int ans = 0;
for (int i = 1; i <= n; i ++)
{
int t = find(i);
if (st[t].count(i)) ans ++;
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
solv();
return 0;
}