Submission #2499996


Source Code Expand

Copy
#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

Submission Time
Task D - Equals
User pankajkhan
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1526 Byte
Status AC
Exec Time 50 ms
Memory 8576 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 4
AC × 23
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt
Case Name Status Exec Time Memory
0_000.txt AC 2 ms 2560 KB
0_001.txt AC 2 ms 2560 KB
0_002.txt AC 2 ms 2560 KB
0_003.txt AC 2 ms 2560 KB
1_004.txt AC 17 ms 3584 KB
1_005.txt AC 28 ms 4352 KB
1_006.txt AC 50 ms 8576 KB
1_007.txt AC 2 ms 2560 KB
1_008.txt AC 2 ms 2560 KB
1_009.txt AC 2 ms 2560 KB
1_010.txt AC 2 ms 2560 KB
1_011.txt AC 2 ms 2560 KB
1_012.txt AC 2 ms 2560 KB
1_013.txt AC 2 ms 2688 KB
1_014.txt AC 3 ms 2688 KB
1_015.txt AC 2 ms 2688 KB
1_016.txt AC 2 ms 2688 KB
1_017.txt AC 3 ms 2688 KB
1_018.txt AC 16 ms 3712 KB
1_019.txt AC 11 ms 3328 KB
1_020.txt AC 11 ms 3456 KB
1_021.txt AC 11 ms 3456 KB
1_022.txt AC 47 ms 7040 KB