Здравствуйте, возможно, вопрос немного глупый, но все же... Недавно я решил попробывать решить задачу по нахождению количества компонентов связности в графе, а потом уже сколько нужно ребер чтобы связать этот граф. Данную задачу я пробывал решать методом непересекающихся множеств. Вот реализация на Delphi(з книги "Алгоритмы: построение и анализ" Т.Кормен и др.):

program Project2;

{$APPTYPE CONSOLE}

var
     f:text;
     n,k,i,st,e,r:integer;
     p,rank:array[1..100000] of integer;

      procedure link(x,y:integer);
     begin
     if (rank[y]>rank[x]) then p[y]:=x else  p[x]:=y;
     if (rank[y]=rank[x]) then inc(rank[y]);
     end;

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

     procedure union(x,y:integer);
     begin
    link(find_set(x),find_set(y));
     end;

begin
assign(f,'input.txt');
reset(f);
readln(f,n,k);
fillchar(rank,n,0);
for i:=1 to n do p[i]:=i;

for i:=1 to k do
begin
readln(f,st,e);
union(st,e);
end;

close(f);
r:=0;
for i:=1 to n do
begin
if (p[i]=i) then r:=r+1;
end;
 assign(f,'output.txt');
 rewrite(f);
 writeln(f,r-1);
 close(f);
end.  

Вот вторая реализация на Delphi(з сайта e-maxx.ru):

program Project2;

{$APPTYPE CONSOLE}
{$N+,R-}
uses SySUtils;

var
  f:text;
   n,k,s,i,st,e,r,a,b:integer;
 p,rank:array[0..100001] of integer;


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

 procedure union(x,y:integer);

  procedure swap(var a,b:integer);
  var
  c:integer;
  begin
  c:=a;
  a:=b;
  b:=c;
  end;

 begin
 a:=find_set(x);
 b:=find_set(y);
 if (a<>b) then
 begin
 if (rank[b]>rank[a]) then swap(a,b); p[b]:=a;
 if (rank[b]=rank[a]) then rank[b]:=rank[b]+1;
 end;

 end;



begin
readln(n,k);
for i:=1 to n do begin p[i]:=i; rank[i]:=0;   end;

for i:=1 to k do
begin
readln(st,e);
union(st,e);
end;


r:=0;
for i:=1 to n do
begin
if (p[i]=i) then r:=r+1;
end;

writeln(r-1);
readln;
end. 

Вопрос: есть ли тесты, при которых программа выдаст ошибку исполнения?(N — количество вершин,К — количество ребер графа)

1) A^B mod C, (1 ≤ A, B, C < 2⁶³).
     При меньших входящих числах я решил задачу методом постепенного возведения в квадрат. Но при данных числах задача будет решена частично, потому что в вычислениях есть операция d*d mod c (d-переменная, которая может принимать максимальное значение 2⁶³ -1). Сначала вычисляется d*d и на этом шагу число не помещается в типы данных. Есть ли способ, который помог бы избежать этого?

2) Извлечение корня квадратного ( только целого числа) из длинного числа A.
  Я пробывал решить задачу методом половинного деления, но при A=10¹⁰⁰ программа уже работает примерно 2 сек. Есть ли алгоритм, который вычисляет корень быстрее и если да, то какой его принцып работы?