Submission #2511623

---

Source Code Expand

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 100005
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
#define mp make_pair
#define ff first
#define ss second

int n,m,tot;
int p[maxn],now[maxn],pre[maxn*2],son[maxn*2];

inline int read(){
	int x=0,f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

void add(int a,int b){son[++tot]=b,pre[tot]=now[a],now[a]=tot;}
void link(int a,int b){add(a,b),add(b,a);}

int top,stack[maxn];
bool vis[maxn],app[maxn];

void dfs(int x){
	vis[x]=app[x]=1; stack[++top]=x;
	for (int p=now[x];p;p=pre[p])
		if (!vis[son[p]]) dfs(son[p]);
}

int main(){
	n=read(),m=read();
	for (int i=1;i<=n;i++) p[i]=read();
	for (int i=1,x,y;i<=m;i++) x=read(),y=read(),link(x,y);
	int ans=0;
	for (int i=1;i<=n;i++)
		if (!vis[i]){
			dfs(i);
			for (int j=1;j<=top;j++)
				ans+=app[p[stack[j]]];
			while (top) app[stack[top--]]=0;
		}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result