Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- const int maxn = 100005;
- int idx[maxn];
- int sz[maxn];
- int n;
- void init() {
- for(int i = 0; i < maxn; i++) {
- idx[i] = i;
- sz[i] = 1;
- }
- }
- int root(int x) {
- while(idx[x] != x) {
- idx[x] = idx[idx[x]];
- x = idx[x];
- }
- return x;
- }
- void join(int A, int B) {
- int root_A = root(A);
- int root_B = root(B);
- if(root_A != root_B) {
- if(sz[root_A] < sz[root_B]) {
- idx[root_A] = idx[root_B];
- sz[root_B] += sz[root_A];
- }
- else {
- idx[root_B] = idx[root_A];
- sz[root_A] += sz[root_B];
- }
- }
- }
- bool check(int A, int B) {
- return root(A) == root(B);
- }
- int main()
- {
- cin >> n;
- init();
- vector<int> v(n);
- for(int i = 0; i < n; i++) {
- cin >> v[i];
- }
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < n; j++) {
- if(v[i] == v[j] - 1 or v[i] == v[j] + 1) {
- join(i, j);
- }
- }
- }
- int res = 0;
- for(int i = 0; i < n; i++) {
- res = max(res, sz[i]);
- }
- cout << res << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement