Submission #2499996

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define N 100005
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false);cin.tie(0)
#define prec(n) fixed<<setprecision(n)

#define pii pair<int,int> 
#define pll pair<ll,ll> 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define vi vector<int> 
#define vll vector<ll>
#define all(c) c.begin(),c.end()
#define tr(it,c) for( typeof(c.begin()) it = c.begin() ; it!=c.end() ; it++)

ll modulo(ll num){ return ((num%mod)+mod)%mod;} // for negative integer
ll power(ll b,ll e,ll MOD=mod){ll ans=1; while(e){if(e%2) ans=(ans*b)%MOD; b=(b*b)%MOD; e/=2;} return ans;}
ll inv(ll num,ll MOD=mod){ return power(modulo(num),mod-2,MOD); }

vi adj[N] ;
int comp[N]={},cnt=0;

void dfs(int u)
{
    comp[u]=cnt;
    for(int i=0;i<adj[u].size();i++)
    {
        if(!comp[adj[u][i]]) dfs(adj[u][i]);
    }
}

int main()
{
    boost;
    
    int n,m,a[N],x,y,i,ans=0; 
    cin>>n>>m; 
    
    for(i=1;i<=n;i++) cin>>a[i];
    
    for(i=0;i<m;i++)
    {
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    
    for(i=1;i<=n;i++)
    {
        if(!comp[i])
        {
            cnt++;
            dfs(i);
        }
    }
       
    for(i=1;i<=n;i++)
    {
        if(a[i]==i) ans++ ; 
        else
        {
            if(comp[i]==comp[a[i]]) ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Submission Info

Judge Result