Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của happyboy99x

#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdio>
using namespace std;

struct Edge {
    int vertex1;
    int vertex2;
    int weight;

    Edge() {
    }

    Edge(int vertex1, int vertex2, int weight): vertex1 (vertex1), vertex2 (vertex2), weight (weight) {
    }

    bool operator < (const Edge &e) const {
        return weight < e.weight;
    }
};

const int N = 1000;
int label[N * N];
int version[N * N];
Edge edges[2 * N * N];
int n;
int a[N][N];
int setVersion;

int convert(int i, int j) {
    return i * n + j;
}

int getSet(int u) {
    if (version[u] != setVersion) {
        version[u] = setVersion;
        label[u] = -1;
    }
    return label[u] < 0 ? u : label[u] = getSet(label[u]);
}

void joinSet(int u, int v) {
    u = getSet(u);
    v = getSet(v);
    if (u == v) return;
    if (label[u] < label[v]) swap(u, v);
    label[v] += label[u];
    label[u] = v;
}

int main() {
#ifndef ONLINE_JUDGE
    assert(freopen("rselect.inp", "r", stdin));
    assert(freopen("rselect.out", "w", stdout));
#endif
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
        }
    }
    int m = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i + 1 < n) edges[m++] = Edge(convert(i, j), convert(i + 1, j), abs(a[i][j] - a[i + 1][j]));
            if (j + 1 < n) edges[m++] = Edge(convert(i, j), convert(i, j + 1), abs(a[i][j] - a[i][j + 1]));
        }
    }
    sort(edges, edges + m);
    int answer = 1;
    for (int i = 0; i < m; ) {
        int j = i;
        while (j < m && edges[i].weight == edges[j].weight) ++j;
        ++setVersion;
        for (int k = i; k < j; ++k) {
            joinSet(edges[k].vertex1, edges[k].vertex2);
            answer = max(answer, -label[getSet(edges[k].vertex1)]);
        }
        i = j;
    }
    cout << answer << '\n';
    return 0;
}

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <string>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(i, a) for(typeof((a).begin()) i = (a).begin(); i != (a).end(); i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int((a).size()))
#define VI vector<int>
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define MP make_pair
#define PB push_back

const int dx[] = {1, 0};
const int dy[] = {0, -1};
const int N = 1010;
const int M = N * N * 4;

using namespace std;

int lab[M];
int a[N][N];
int cnt[M];
bool was[M], wasCnt[M];
int n, ans;
VI undo, undoCnt;

struct edge {
    int u, v, diff;
    edge(int _u, int _v, int _d) {
        u = _u; v = _v; diff = _d;
    }
    bool operator < (const edge& b) const {
        return diff < b.diff;
    }
};
vector<edge> e;

int root(int u) {
    if (lab[u] <= 0) return u;
    return root(lab[u]);
}

void join(int u, int v) {
    if (lab[u] > lab[v]) swap(u, v);
    if (lab[u] == lab[v]) lab[u]--;
    lab[v] = u; cnt[u] += cnt[v];
    if (lab[v] && !was[v]) {
        was[v] = 1; undo.PB(v);
    }
    if (lab[u] && !was[u]) {
        was[u] = 1; undo.PB(u);
    }
    if (cnt[u] != 1 && !wasCnt[u]) {
        wasCnt[u] = 1;
        undoCnt.PB(u);
    }
    ans = max(ans, cnt[u]);
}

bool inside(int x, int y) {
    return x > 0 && y > 0 && x <= n && y <= n;
}

int id(int x, int y) {
    return (x - 1) * n + y;
}

void initEdges() {
    REP(i, 1, n) REP(j, 1, n) REP(d, 0, 2) {
        int x = i + dx[d], y = j + dy[d];
        if (inside(x, y)) e.PB(edge(id(i, j), id(x, y), abs(a[i][j] - a[x][y])));
    }
    sort(ALL(e));
}

void solve(int l, int r) {
    REP(i, l, r) {
        int x = root(e[i].u), y = root(e[i].v);
        if (x != y) join(x, y);
    }
    while (!undo.empty()) {
        was[undo.back()] = 0;
        lab[undo.back()] = 0;
        undo.pop_back();
    }
    while (!undoCnt.empty()) {
        wasCnt[undoCnt.back()] = 0;
        cnt[undoCnt.back()] = 1;
        undoCnt.pop_back();
    }
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    REP(i, 1, n) REP(j, 1, n) cin >> a[i][j];
    initEdges();
    REP(i, 1, n * n) cnt[i] = 1;

    int j;
    for(int i = 0; i < SZ(e); i = j + 1) {
        j = i;
        while (j < SZ(e) && e[j + 1].diff == e[i].diff) j++;
        solve(i, j);
    }
    cout << ans;
    return 0;
}

Code mẫu của RR

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <complex>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>
using namespace std;

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)

#define DEBUG(x) { cout << #x << " = " << x << endl; }
#define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
#define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }

int n, a[1011][1011];
int id[1011][1011];

int lab[1000111];
int getRoot(int u) {
    if (lab[u] < 0) return u;
    return lab[u] = getRoot(lab[u]);
}
void merge(int u, int v) {
    u = getRoot(u); v = getRoot(v);
    if (u == v) return ;

    int x = lab[u] + lab[v];
    if (lab[u] < lab[v]) lab[u] = x, lab[v] = u;
    else lab[v] = x, lab[u] = v;
}

vector< pair<int,int> > ls[1000111];
int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL);
    cout << (fixed) << setprecision(6);
    while (cin >> n) {
        FOR(i,1,n) FOR(j,1,n) cin >> a[i][j];
        int cur = 0;
        FOR(i,1,n) FOR(j,1,n) id[i][j] = ++cur;
        FOR(i,1,n) FOR(j,1,n) {
            FOR(di,-1,1) FOR(dj,-1,1)
                if (di * di + dj * dj == 1) {
                    int ii = i + di, jj = j + dj;
                    if (ii < 1 || ii > n || jj < 1 || jj > n) continue;

                    if (a[i][j] < a[ii][jj]) continue;
                    ls[a[i][j] - a[ii][jj]].push_back(make_pair(id[i][j], id[ii][jj]));
                }
        }
        int res = 0;
        memset(lab, -1, sizeof lab);
        REP(val,1000111) {
            REP(i,ls[val].size()) {
                pair<int,int> e = ls[val][i];
                int u = e.first, v = e.second;
                if (getRoot(u) == getRoot(v)) continue;

                merge(u, v);
                res = max(res, -lab[getRoot(u)]);
                res = max(res, -lab[getRoot(v)]);
            }
            REP(i,ls[val].size()) {
                pair<int,int> e = ls[val][i];
                lab[e.first] = lab[e.second] = -1;
            }
        }
        cout << res << endl;
    }
    return 0;
}

Code mẫu của skyvn97

#include<algorithm>
#include<cstdio>
#include<vector>
#define MAX   1010
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define fi   first
#define se   second
using namespace std;
class DisjointSet {
    private:
    int n;
    vector<int> up,need;
    vector<bool> changed;
    void update(int x,int v) {
        if (!changed[x]) need.push_back(x);
        changed[x]=true;
        up[x]=v;
    }
    int find(int x) {
        if (up[x]<0) return (x);
        update(x,find(up[x]));
        return (up[x]);
    }
    public:
    DisjointSet() {
        n=0;
    }
    DisjointSet(int n) {
        this->n=n;
        up.assign(n+7,-1);
        changed.assign(n+7,false);
    }
    void reset(void) {
        while (!need.empty()) {
            int x=need.back();need.pop_back();
            up[x]=-1;
            changed[x]=false;
        }
    }
    int join(int a,int b) {
        int x=find(a);
        int y=find(b);
        if (x==y) return (-up[x]);
        if (up[x]>up[y]) swap(x,y);
        int res=up[x]+up[y];
        update(x,res);
        update(y,x);
        return (-res);
    }
};
struct Edge {
    int u,v,c;
    Edge() {
        u=v=c=0;
    }
    Edge(int _u,int _v,int _c) {
        u=_u;v=_v;c=_c;
    }
    bool operator < (const Edge &e) const {
        return (c<e.c);
    }
};
int a[MAX][MAX];
int n;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
void init(void) {
    scanf("%d",&n);
    FOR(i,1,n) FOR(j,1,n) scanf("%d",&a[i][j]);
}
int cellID(int x,int y) {
    return ((x-1)*n+y);
}
int Abs(int x) {
    return (x<0?-x:x);
}
bool inside(int x,int y) {
    if (x<1 || x>n || y<1 || y>n) return (false);
    return (true);
}
void process(void) {
    vector<Edge> edge;
    FOR(i,1,n) FOR(j,1,n) REP(k,4) if (inside(i+dx[k],j+dy[k])) {
        int x=i+dx[k];
        int y=j+dy[k];
        if (cellID(i,j)<cellID(x,y)) edge.push_back(Edge(cellID(i,j),cellID(x,y),Abs(a[i][j]-a[x][y])));
    }
    sort(edge.begin(),edge.end());
    int res=1;
    DisjointSet dsu(n*n);
    REP(i,edge.size()) {
        if (i>0 && edge[i].c!=edge[i-1].c) dsu.reset();
        res=max(res,dsu.join(edge[i].u,edge[i].v));
    }
    printf("%d\n",res);
}
int main(void) {
    //freopen("RSELECT.INP","r",stdin);
    //freopen("RSELECT.OUT","w",stdout);
    init();
    process();
    return 0;
}