Submission #8425706
Source Code Expand
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define swap(a, b, type) { type _tmp = a; a = b; b = _tmp; }
typedef long long ll;
typedef unsigned long long ull;
/*================================================
Disjoint Set
================================================*/
class DisjointSet {
private:
vector<int> rank, p;
void link(int x, int y) {
if (rank[x] > rank[y]) {
p[y] = x;
}
else {
p[x] = y;
if (rank[x] == rank[y]) rank[y]++;
}
}
int findSet(int x) {
if (x != p[x]) p[x] = findSet(p[x]);
return p[x];
}
public:
DisjointSet() {}
DisjointSet(int size) {
rank.resize(size, 0);
p.resize(size, 0);
repc(i, 1, size) makeSet(i);
}
void makeSet(int x) {
p[x] = x;
rank[x] = 0;
}
bool same(int x, int y) {
return findSet(x) == findSet(y);
}
void unite(int x, int y) {
link(findSet(x), findSet(y));
}
};
int pp[100001];
int main()
{
int N, M, x, y, ans = 0;
cin >> N >> M;
repc(i, 1, N) cin >> pp[i];
DisjointSet DS = DisjointSet(N + 1);
rep(i, M) {
cin >> x >> y;
DS.unite(x, y);
}
repc(i, 1, N) {
if (DS.same(i, pp[i])) ans++;
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Equals |
User |
ChiliAct |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1612 Byte |
Status |
RE |
Exec Time |
97 ms |
Memory |
1408 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 400 |
Status |
|
|
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 |
RE |
96 ms |
256 KB |
0_001.txt |
AC |
1 ms |
256 KB |
0_002.txt |
AC |
1 ms |
256 KB |
0_003.txt |
RE |
97 ms |
256 KB |
1_004.txt |
AC |
43 ms |
256 KB |
1_005.txt |
AC |
84 ms |
1408 KB |
1_006.txt |
AC |
89 ms |
1408 KB |
1_007.txt |
AC |
1 ms |
256 KB |
1_008.txt |
AC |
1 ms |
256 KB |
1_009.txt |
AC |
1 ms |
256 KB |
1_010.txt |
AC |
1 ms |
256 KB |
1_011.txt |
AC |
1 ms |
256 KB |
1_012.txt |
AC |
1 ms |
256 KB |
1_013.txt |
AC |
2 ms |
256 KB |
1_014.txt |
AC |
3 ms |
256 KB |
1_015.txt |
AC |
1 ms |
256 KB |
1_016.txt |
AC |
1 ms |
256 KB |
1_017.txt |
AC |
2 ms |
256 KB |
1_018.txt |
AC |
39 ms |
256 KB |
1_019.txt |
AC |
32 ms |
1408 KB |
1_020.txt |
AC |
29 ms |
1408 KB |
1_021.txt |
AC |
30 ms |
1408 KB |
1_022.txt |
AC |
88 ms |
1408 KB |