Submission #2560099

---

Source Code Expand

#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <set>
#include <map>
using namespace std;

const int MAX_UF = 210000;
struct UnionFind {
	int size_uf;
	int par[MAX_UF];
	int rank[MAX_UF];
	int size_component[MAX_UF];

	UnionFind(int n = 0) { size_uf = n; for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, size_component[i] = 1; }
	void init(int n) { size_uf = n; for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, size_component[i] = 1; }
	int root(int x) { return par[x] == x ? x : par[x] = root(par[x]); }
	bool issame(int x, int y) { return root(x) == root(y); }
	int size(int x) { return size_component[root(x)]; }

	void connect(int x, int y) {
		x = root(x), y = root(y);
		int sx = size_component[x], sy = size_component[y];
		if (x == y) return;
		int r;
		if (rank[x] < rank[y]) par[x] = y, r = y;
		else { par[y] = x, r = x; if (rank[x] == rank[y]) ++rank[x]; }
		size_component[r] = sx + sy;
	}
} uf;

int N, M;
vector<int> P;

int main() {
  cin >> N >> M;
  P.resize(N);
  for (int i = 0; i < N; ++i) {
	cin >> P[i];
	--P[i];
  }
  uf.init(N);
  for (int i = 0; i < M; ++i) {
	int x, y;
	cin >> x >> y;
	--x, --y;
	uf.connect(x, y);
  }

  long long res = 0;
  
  map<int,set<int> > perm, index;
  for (int i = 0; i < N; ++i) {
	int r = uf.root(i);
	perm[r].insert(P[i]);
	index[r].insert(i);
  }

  for (map<int,set<int> >::iterator it = perm.begin(); it != perm.end(); ++it) {
	long long tmp = 0;
	int r = it->first;
	set<int> se = it->second;
	for (set<int>::iterator it2 = se.begin(); it2 != se.end(); ++it2) {
	  if (index[r].count(*it2)) ++tmp;
	}
	res += tmp;
  }

  cout << res << endl;
}







  

Submission Info

Judge Result