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=100010;
var n:longint;
    a,re,pre,d:array[1..maxn] of longint;

procedure rf;
var i:longint;
begin
     assign(input,fi); reset(input);
     read(n);
     for i:=1 to n do read(a[i]);
     close(input);
end;

procedure pr;
var i,j,dem,x,t:longint;
begin
     for i:=1 to n do
         if re[i]=0 then
         begin
              if a[i]=i then
              begin
                   re[i]:=1; d[i]:=1;
              end;
              if a[i]<i then
              begin
                   re[i]:=re[a[i]]+1;
                   d[i]:=1;
              end;
              if a[i]>i then
              begin
                   re[i]:=1; j:=i;
                   while re[a[j]]=0 do
                   begin
                        re[a[j]]:=re[j]+1;
                        pre[a[j]]:=j;
                        j:=a[j];
                   end;
                   x:=a[j];
                   if d[x]=1 then
                   begin
                        while j<>i do
                        begin
                             re[j]:=re[a[j]]+1;
                             d[j]:=1;
                             j:=pre[j];
                        end;
                        re[i]:=re[a[i]]+1;
                        d[i]:=1;
                        continue;
                   end;
                   t:=re[j]-re[x]+1;
                   while j<>x do
                   begin
                        re[j]:=t;
                        d[j]:=1;
                        j:=pre[j];
                   end;
                   re[x]:=t; d[x]:=1;
                   if x=i then continue;
                   j:=pre[x];
                   while j<>i do
                   begin
                        re[j]:=re[a[j]]+1;
                        d[j]:=1;
                        j:=pre[j];
                   end;
                   re[i]:=re[a[i]]+1;
                   d[i]:=1;
              end;
         end;
end;

procedure wf;
var i:longint;
begin
     assign(output,fo); rewrite(output);
     for i:=1 to n do writeln(re[i]);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<stack>
#include<cassert>
using namespace std;

const int N = 100000;
int next[N], n, d[N], candy[N];

void enter() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &next[i]);
        --next[i];
    }
}

void start(int u, int &time) {
    stack<int> st; st.push(u);
    d[u] = ++time;
    while(true) {
        int v = next[u];
        if(d[v] == 0) st.push(v), d[v] = ++time;
        else {
            int x = candy[v] != 0 ? candy[v] + 1 : d[u] - d[v] + 1;
            bool back = candy[v] != 0;
            for(; !st.empty(); st.pop()) {
                int w = st.top();
                candy[w] = x;
                if(w == v) back = true;
                if(back) ++x;
            }
            break;
        }
        u = v;
    }
}

void solve() {
    int time = 0;
    for(int u = 0; u < n; ++u)
        if(d[u] == 0) start(u, time);
}

void print() {
    for(int u = 0; u < n; ++u)
        printf("%d\n", candy[u]);
}

int main() {
    enter();
    solve();
    print();
    return 0;
}

Code mẫu của ladpro98

program treat;
uses    math;
const   maxn=123456;
        fi='';
var     a,s,f:array[1..maxn] of longint;
        check,instack:array[1..maxn] of boolean;
        n,top:longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        readln(inp,a[i]);
        close(inp);
end;

procedure process;
var     i,j,t,tt,d:longint;
begin

        for i:=1 to n do
        begin
                if check[i] then continue;
                j:=i;top:=0;
                while true do
                begin
                        if check[j] then
                        begin
                                inc(top);s[top]:=j;
                                for t:=top-1 downto 1 do
                                begin
                                        check[s[t]]:=true;
                                        f[s[t]]:=1+f[s[t+1]];
                                end;
                                break;
                        end
                        else
                        if inStack[j] then
                        begin
                                d:=0;
                                for t:=top downto 1 do
                                begin
                                        inc(d);
                                        if s[t]=j then break;
                                end;
                                for tt:=top downto t do
                                begin
                                        check[s[tt]]:=true;
                                        f[s[tt]]:=d;
                                end;
                                top:=t;
                                for t:=top-1 downto 1 do
                                begin
                                        check[s[t]]:=true;
                                        f[s[t]]:=1+f[s[t+1]];
                                end;
                                break;
                        end;
                        inStack[j]:=true;
                        inc(top);
                        s[top]:=j;
                        j:=a[j];
                end;
        end;
end;

procedure output;
var     i:longint;
begin
        for i:=1 to n do
        writeln(f[i]);

end;

begin
        input;
        process;
        output;
end.

Code mẫu của RR

{$R-,Q-}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=100000;
type
  list=^node;
  node=record
         u:longint;
         next:list;
       end;
var
  f1,f2:text;
  tt,sl,count,top,n:longint;
  d,ss,dd,sd,vao,ra,stack,xet,ke:array[1..MAXN] of longint;
  ds:array[1..MAXN] of list;
procedure add(u:longint; var a:list); inline;
var
  p:list;
begin
  new(p); p^.u:=u;
  p^.next:=a; a:=p;
end;
procedure openF; inline;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
  close(f1); close(f2);
end;
procedure inp; inline;
var
  i:longint;
begin
  read(f1,n);
  for i:=1 to n do read(f1,ke[i]);
end;
procedure dfs1(u:longint);
var
  v:longint;
begin
  tt:=1; ss[1]:=u;
  while tt>0 do
    begin
      u:=ss[tt]; dec(tt);
      if vao[u]=0 then
        begin
          inc(count);
          vao[u]:=count;
          xet[u]:=1;
        end;
      v:=ke[u];
      if xet[v]=0 then
        begin
          inc(tt); ss[tt]:=u;
          inc(tt); ss[tt]:=v;
        end
      else
        begin
          inc(count);
          ra[u]:=count;
        end;
    end;
end;
procedure dfs2(u:longint);
var
  k,v:longint;
begin
  tt:=1; ss[tt]:=u;
  while tt>0 do
    begin
      u:=ss[tt]; dec(tt);
      inc(top); stack[top]:=u;
      xet[u]:=1;
      v:=ke[u];
      if (xet[v]=1) then
        begin
          if (vao[v]<=vao[u]) and (ra[v]>=ra[u]) then
            begin
              inc(sl); sd[sl]:=0;
              repeat
                inc(sd[sl]);
                k:=stack[top]; dec(top);
                add(k,ds[sl]); dd[k]:=sl;
              until k=v;
            end;
        end
      else
        begin
          inc(tt); ss[tt]:=v;
        end;
    end;
end;
procedure dfs3(u:longint);
var
  v:longint;
begin
  tt:=1; ss[1]:=u;
  while tt>0 do
    begin
      u:=ss[tt]; dec(tt);
      v:=ke[u];
      if d[v]=0 then
        begin
          inc(tt); ss[tt]:=u;
          inc(tt); ss[tt]:=v;
        end
      else d[u]:=d[v]+1;
    end;
end;
procedure solve;
var
  i,u,x:longint;
begin
  fillchar(xet,sizeof(xet),0); count:=0;
  for i:=1 to n do
    if xet[i]=0 then dfs1(i);
  fillchar(xet,sizeof(xet),0);
  for i:=1 to n do
    if xet[i]=0 then
      begin
        top:=0;
        dfs2(i);
      end;
  fillchar(xet,sizeof(xet),0);
  for i:=1 to n do
    if dd[i]>0 then
      begin
        xet[i]:=1;
        d[i]:=sd[dd[i]];
      end;
  for i:=1 to n do
    if xet[i]=0 then
      begin
        dfs3(i);
        writeln(f2,d[i]);
      end
    else writeln(f2,d[i]);
end;
begin
  openF;
  inp;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
long a[100001],n,t,N[100001],f[100001];
void di(long x,long y)
  {
  a[x]=y;
  t=N[x];
  while(t!=x)
    {
    f[t]=1;
    a[t]=y;
    t=N[t];
    }
  }  
main()
{
scanf("%ld",&n);
for(long i=1;i<=n;i++)
  {
  scanf("%ld",&N[i]);
  a[i]=0;f[i]=0;
  }
for(long i=1;i<=n;i++)
  {
  //printf("0 ");
  if(f[i]!=0)
    continue;
  else
    {
    f[i]=1;
    t=N[i];
    a[i]=1;         
    while(1)
      {
      if(t==i)
        {
        di(i,a[i]);
        break;
        }
      else if(f[t]!=0&&a[t]!=0)
        {
        //printf("0 ");
        a[i]=a[i]+a[t];
        long u=N[i];
        a[u]=a[i]-1;
        while(u!=t)
          {
          f[u]=1;
          a[N[u]]=a[u]-1;
          u=N[u];
          }
        break;  
        } 
      else if(f[t]!=0&&a[t]==0)
        {
        //printf("? ");
        long u=N[i];
        a[u]=a[i]-1;
        while(u!=t)
          {
          //printf("1 ");
          f[u]=1;
          a[N[u]]=a[u]-1;
          u=N[u];
          }
        di(t,a[t]);
        break;
        }
      else    
        {
        //printf("2 ");
        a[i]++;
        f[t]=1;
        t=N[t];
        }
      }
    }
  }
for(long i=1;i<=n;i++)
  printf("%ld\n",a[i]);
//getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
program treat;
const
  input  = '';
  output = '';
  maxn = 100000;
var
  stack,next,res,list,num,low: array[1..maxn] of integer;
  free: array[1..maxn] of boolean;
  n,count,top,nlist: integer;

procedure init;
var
  f: text;
  i: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, n);
  for i := 1 to n do read(f, next[i]);

  close(f);
end;

procedure push(v: integer);
begin
  inc(top);
  stack[top] := v;
end;

function pop: integer;
begin
  pop := stack[top];
  dec(top);
end;

procedure dfs(u: integer);
var
  v,i: integer;
begin
  inc(count);
  num[u] := count;
  low[u] := num[u];
  push(u);

  v:= next[u];
  if v = u then
    begin
      res[u] := 1;
      free[u] := false;
      exit;
    end;

  if not free[v] then
    begin
      res[u] := res[v] + 1;
      free[u] := false;
      exit;
    end;

  if num[v] = 0 then
    begin
      dfs(v);
      if not free[v] then
        begin
          res[u] := res[v] + 1;
          free[u] := false;
          exit;
        end;
      if low[u] > low[v] then low[u] := low[v];
    end
  else
    if low[u] > num[v] then low[u] := num[v];

  if num[u] = low[u] then
    begin
      nlist := 0;
      repeat
        v := pop;
        inc(nlist);
        list[nlist] := v;
        free[v] := false;
      until v = u;

      for i := 1 to nlist do res[list[i]] := nlist;
    end;
end;

procedure solve;
var
  i: integer;
begin
  fillchar(res, sizeof(res), 0);
  fillchar(free, sizeof(free), true);
  count := 0;
  top := 0;

  for i := 1 to n do
    if free[i] then dfs(i);
end;

procedure printresult;
var
  f: text;
  i: integer;
begin
  assign(f, output);
    rewrite(f);
    for i := 1 to n do writeln(f, res[i]);
  close(f);
end;

begin
  init;
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#define MAX   100100
using namespace std;
int next[MAX];
vector<int> g[MAX];
vector<int> h[MAX];
int low[MAX];
int num[MAX];
int res[MAX];
int ncp[MAX];
int sz[MAX];
int p[MAX];
int c[MAX];
int l[MAX];
bool fre[MAX];
int n,m,nc;
int cnt;
stack<int> s;
queue<int> q;
void loadgraph_1st(void) {
    int i;
    scanf("%d",&n);
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&next[i]);
        g[i].clear();
        g[i].push_back(next[i]);
    }   
    memset(low,0,sizeof low);
    memset(num,0,sizeof num);
    memset(fre,true,sizeof fre);
    while (!s.empty()) s.pop();
}
int min(const int &x,const int &y) {
    if (x<y) return (x); else return (y);
}
void visit(const int &u) {
    int i,v;
    cnt++;
    num[u]=cnt;
    low[u]=num[u];
    s.push(u);
    for (i=0;i<g[u].size();i=i+1) {
        v=g[u][i];
        if (!fre[v]) continue;
        if (num[v]==0) {
            visit(v);
            low[u]=min(low[u],low[v]);
        }
        else low[u]=min(low[u],num[v]);
    }
    if (low[u]==num[u]) {
        nc++;
        sz[nc]=0;
        do {
            v=s.top();s.pop();
            ncp[v]=nc;
            sz[nc]++;
            fre[v]=false;
        }
        while (v!=u);
    }
}
void tarjan(void) {
    int i;
    nc=0;
    cnt=0;
    for (i=1;i<=n;i=i+1)
        if (num[i]==0) visit(i);
}
void BFS(const int &s) {
    int i,x;
    while (!q.empty()) q.pop();
    q.push(s);
    c[s]=1;
    p[s]=s;
    while (!q.empty()) {
        x=q.front();q.pop();
        for (i=0;i<h[x].size();i=i+1)
            if (c[h[x][i]]==0) {
                c[h[x][i]]=1;
                l[h[x][i]]=l[x]+1;
                p[h[x][i]]=s;
                q.push(h[x][i]);
            }
    }
}
void loadgraph_2nd(void) {
    int i;
    for (i=1;i<=nc;i=i+1) h[i].clear();
    for (i=1;i<=n;i=i+1)
        h[ncp[next[i]]].push_back(ncp[i]);
    memset(l,0,sizeof l);
    memset(c,0,sizeof c);   
    for (i=1;i<=nc;i=i+1)
        if (c[i]==0 && sz[i]>1) BFS(i); 
    for (i=1;i<=nc;i=i+1)
        if (c[i]==0) BFS(i);
}
void count_res(void) {
    int i;
    for (i=1;i<=n;i=i+1) {
        if (i==next[i]) res[i]=1;
        else res[i]=l[ncp[i]]+sz[p[ncp[i]]];
    }
    for (i=1;i<=n;i=i+1) printf("%d\n",res[i]);
}
int main(void) {
    loadgraph_1st();
    tarjan();
    loadgraph_2nd();
    count_res();
    return 0;
}

Code mẫu của khuc_tuan

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

int n, next[100010];
int f[100010];
bool mark[100010];

int main() {
    scanf("%d", &n);
    for(int i=1;i<=n;++i)
        scanf("%d", next + i);
    for(int i=1;i<=n;++i)
        if(f[i]==0) {
            vector<int> ds;
            ds.push_back(i);
            mark[i] = true;
            int z = i;
            while(true) {
                z = next[z];
                if(mark[z]) break;
                if(f[z]>0) {
                    for(int j=0;j<ds.size();++j) f[ds[j]] = f[z] + ds.size() - j;
                    goto theend;
                }
                mark[z] = true;
                ds.push_back(z);
            }
            for(int j=0;j<ds.size();++j) if(ds[j]==z) {
                int ct = ds.size() - j;
                for(int k=j;k<ds.size();++k) f[ds[k]] = ct;
                for(int k=j-1;k>=0;--k) f[ds[k]] = ct + j - k;
                break;  
            }
            theend : ;
            for(int j=0;j<ds.size();++j) mark[ds[j]] = false;
        }
    for(int i=1;i<=n;++i)
        printf("%d\n", f[i]);
    // system("pause");
    return 0;
}