abc097d<并查集，排列>-526互联

题目

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;
}