ARC097D Equals

题目

We have a permutation of the integers from 1 through N, p₁, p₂, .., p_N. We also have M pairs of two integers between 1 and N (inclusive), represented as (x₁,y₁), (x₂,y₂), .., (x_M,y_M). AtCoDeer the deer is going to perform the following operation on p as many times as desired so that the number of i (1 ≤ i ≤ N) such that p_i=i is maximized:

Choose j such that 1 ≤ j ≤ M, and swap p_{x_j} and p_{y_j}.

Find the maximum possible number of i such that p_i=i after operations.

Constraints

2 ≤ N ≤ 10⁵
1 ≤ M ≤ 10⁵
p is a permutation of integers from 1 through N.
1 ≤ x_j,y_j ≤ N
x_j ≠ y_j
If i ≠ j, {x_i,y_i} ≠ {x_j,y_j}.
All values in input are integers

Input

Input is given from Standard Input in the following format:

N M

p₁ p₂ .. p_N

x₁ y₁

x₂ y₂

:

x_M y_M

Output

Print the maximum possible number of i such that p_i=i after operations.

题目大意

给了一个数组，一堆pair，可随意交换任意次pair对应的下标的数，求数组里面下标等于元素值的最多对数。

分析

将初始位置的下标和元素值连边，然后将能互相交换的下标连边，然后Tarjan缩点，判断下标和元素值是否在同一联通分量中即可，注意让代表下标的点与代表元素值的点错开即可

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define pb push_back
int d[110000];
int belong[210000],cnt,sum,dfn[210000],low[210000],ist[210000];
vector<int>v[200010];
stack<int>a;
void tarjan(int x){
    int i,j,k;
    dfn[x]=low[x]=++cnt;
    a.push(x);
    ist[x]=1;
    for(i=0;i<v[x].size();i++)
       if(!dfn[v[x][i]]){
            tarjan(v[x][i]);
            low[x]=min(low[x],low[v[x][i]]);
       }else if(ist[v[x][i]]){
            low[x]=min(low[x],dfn[v[x][i]]);
       }
       if(low[x]==dfn[x]){
          sum++;
          while(1){
              int u=a.top();
              a.pop();
              ist[u]=0;
              belong[u]=sum;
              if(u==x)break;
          }
       }
}
int main()
{   int n,m,i,j,k,x,y;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        cin>>d[i];
        v[i].pb(d[i]+n);
        v[d[i]+n].pb(i);
    }
    for(i=1;i<=m;i++){
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    for(i=1;i<=2*n;i++)
        if(!dfn[i])tarjan(i);
    int ans=0;
        for(i=1;i<=n;i++){
            if(belong[i]==belong[i+n])ans++;
        }
    cout<<ans<<endl;
    return 0;
}

巴特西

ARC097D Equals

最新文章

热门文章