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 flashmt

const fi='';
      fo='';
      maxn=10000;
var cha,nhan:array[1..maxn] of integer;
    n,i,x,y,z,p:longint;

function find(x:longint):longint;
begin
     if x=cha[x] then find:=x
     else
     begin
          cha[x]:=find(cha[x]);
          find:=cha[x];
     end;
end;

procedure hop(x,y:longint);
var a,b:longint;
begin
     a:=find(x); b:=find(y);
     if nhan[a]>nhan[b] then cha[b]:=a
     else
     begin
          if nhan[a]<nhan[b] then cha[a]:=b
          else
          begin
               if a<>b then
               begin
                    cha[b]:=a;
                    nhan[a]:=nhan[a]+1;
               end;
          end;
     end;
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     for i:=1 to maxn do cha[i]:=i;
     readln(p);
     for i:=1 to p do
     begin
          readln(x,y,z);
          if z=1 then hop(x,y)
          else
              if find(x)=find(y) then writeln(1) else writeln(0);
     end;
     close(input); close(output);
end.

Code mẫu của happyboy99x

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

const int N = 10000;
int s[N];

int findSet(int x) {
    return s[x] == x ? x : s[x] = findSet(s[x]);
}

void unionSet(int x, int y) {
    s[findSet(x)] = findSet(y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    for(int i = 0; i < N; ++i)
        s[i] = i;
    int p;
    cin >> p;
    for(int i = 0; i < p; ++i) {
        int x;
        int y;
        int z;
        cin >> x >> y >> z;
        --x; --y;
        if(z == 1) {
            unionSet(x, y);
        } else {
            printf("%d\n", findSet(x) == findSet(y) ? 1 : 0);
        }
    }
    return 0;
}

Code mẫu của ladpro98

//http://vn.spoj.com/problems/IOIBIN/
#include <cstdio>
const int N = 10005;
using namespace std;

struct disjoint_set {
    int P[N];
    disjoint_set() {for(int i = 0; i < N; i++) P[i] = i;}
    int at(int x) {return (x == P[x]) ? P[x] : (P[x] = at(P[x]));}
    void join(int x, int y) {P[at(x)] = at(y);}
};
disjoint_set Lab;

int main()
{
    int x, y, z, q;
    scanf("%d", &q);
    while (q--) {
        scanf("%d %d %d", &x, &y, &z);
        x = Lab.at(x); y = Lab.at(y);
        if (z == 1) {if (x != y) Lab.join(x, y);}
        else {printf("%d\n", x == y ? 1 : 0);}
    }
    return 0;
}

Code mẫu của RR

var
  lab:array[1..10111] of longint;
  i,m:longint;
  x,y,q:longint;

function getRoot(u:longint):longint;
    begin
      if lab[u]<0 then exit(u);
      lab[u]:=getRoot(lab[u]); exit(lab[u]);
    end;

procedure union(r1,r2:longint);
    var
      x:longint;
    begin
      if r1=r2 then exit;
      x:=lab[r1]+lab[r2];
      if lab[r1]<lab[r2] then
        begin
          lab[r1]:=x;
          lab[r2]:=r1;
        end
      else
        begin
          lab[r2]:=x;
          lab[r1]:=r2;
        end;
    end;

begin
  for x:=1 to 10000 do lab[x]:=-1;
  read(m);
  for i:=1 to m do
    begin
      read(x,y,q);
      x:=getRoot(x);
      y:=getRoot(y);
      if q=1 then union(x,y)
      else if x=y then writeln(1)
      else writeln(0);
    end;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
long g[50001],kq[50001],p,x,y,c,i,t;
long goc(long x)
  {
  long b;
  if(g[x]==x)
    return x;
  else
    {
    b=goc(g[x]);
    g[x]=b;
    return b;
    }
  }
void update(long x,long y)
  {
  long gx,gy;
  gx=goc(x);
  gy=goc(y);
  g[gy]=gx;
  }
void check(long x,long y)
  {
  long gx,gy;
  t++;
  gx=goc(x);
  gy=goc(y);
  if(gx==gy)
    kq[t]=1;
  else kq[t]=0;
  }
main()
{
for(i=1;i<=10000;i++)
  g[i]=i;
scanf("%ld",&p);
for(i=1;i<=p;i++)
  {
  scanf("%ld %ld %ld",&x,&y,&c);
  if(c==1) update(x,y);
  else check(x,y);
  }
for(i=1;i<=t;i++)
  printf("%ld\n",kq[i]);
//getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
program ioibin2;
const
  input  = '';
  output = '';
  maxn = 10000;
var
  q: integer;
  fi,fo: text;
  p,rank: array[1..maxn] of integer;

procedure openfile;
begin
  assign(fi, input);
    reset(fi);

  assign(fo, output);
    rewrite(fo);
end;

function root(v: integer): integer;
begin
  if v <> p[v] then p[v] := root(p[v]);
  root := p[v];
end;

procedure union(r1,r2: integer);
begin
  if rank[r1] > rank[r2] then p[r2] := r1 else p[r1] := r2;
  if rank[r1] = rank[r2] then inc(rank[r2]);
end;

procedure solve;
var
  i,x,y,c,r1,r2: integer;
begin
  readln(fi, q);
  for i := 1 to maxn do
    begin
      p[i] := i;
      rank[i] := 0;
    end;

  for i := 1 to q do
    begin
      readln(fi, x, y, c);
      r1 := root(x);
      r2 := root(y);

      if (c = 1) and (r1 <> r2) then union(r1,r2)
      else if c = 2 then
        if r1 = r2 then writeln(fo, 1) else writeln(fo, 0);
    end;
end;

procedure closefile;
begin
  close(fo);
  close(fi);
end;

begin
  openfile;
  solve;
  closefile;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   100100
#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)
using namespace std;
class DisjointSet {
    private:
    vector<int> label; //label[x] stores the root of x if x is not root, otherwise it stores -(size of x's set).
    public:
    DisjointSet(){}
    DisjointSet(int n) {
        label.assign(n+7,-1); //label should contains at least n+1 elements, as x is 1-indexed.
        //At first, each node is a seperate set of size 1.      
    }
    int find(int x) { //find the root of set which contains x.
        if (label[x]<0) return (x); //x is root iff label[x] is negative.
        label[x]=find(label[x]);
        return (label[x]); //find the root of x by recursion.
    }
    bool join(int a,int b) { // join the sets which contains a and b. Return false iff a and b are already in the same set.
        int x=find(a);
        int y=find(b);
        if (x==y) return (false); //A set contains both a and b.
        if (label[x]>label[y]) swap(x,y); //label[x]>label[y] means size(x)<size(y).
        //We speed up the disjoint set by joinning the smaller set to the bigger set        
        label[x]+=label[y];
        label[y]=x; //Update the label of x and y.      
        return (true);
    }
    int getSize(int x) { //return the size of set which contains x.
        return (-label[find(x)]);
    }
};
//This code is used to solve the problem: http://vn.spoj.com/problems/IOIBIN/
int main(void) {
    DisjointSet dsu(MAX);
    int q;
    scanf("%d",&q);
    REP(zz,q) {
        int u,v,t;
        scanf("%d%d%d",&u,&v,&t);
        if (t==1) dsu.join(u,v); else printf("%d\n",dsu.find(u)==dsu.find(v));
    }
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>

using namespace std;

int f[10010];

int root(int i) { return f[i]<0 ? i : root(f[i]); }

int main() {
    int p;
    scanf("%d", &p);
    memset( f, -1, sizeof(f));
    for(int kk=0;kk<p;++kk) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        if(z==1) {
            x = root(x);
            y = root(y);
            if(x!=y) {
                if(f[x]>f[y]) swap(x,y);
                f[x] += f[y];
                f[y] = x;
            }
        }
        else printf("%d\n", root(x)==root(y) ); 
    }   
    return 0;
}