Задача (на графы)

[Witaliy]

Всем привет
Возникла такая задача:
В классе Петрика все дети очень дружные. Среди учеников этого класса выполняется такое правило - друг моего друга мой друг. Также, если Петрик дружит с Андрейком, то Андрейко не обязательно дружит с Петриком. Учительница знает, что некоторые дети дружат, но обо всех она не знает. Все же учительнице хочется узнать, насколько у нее дружеский класс. Для этого Вам нужно определить, сколько существует упорядоченных пар друзей в этом классе (ученики сами с собой не дружат).
1<=N<=500
1<=N<=5000
Вход. Диние:
N-количество учеников в классе, M - количество пар, о которых учительнийца знает, что они дружат. В следующий М рядках указаны ети пары. Все ученики пронумерованние от 1 до N
Вых. Дание:
Количество дружных пар учеников.
Например

2 3
1 2
2 3

Результат: 3

Тепер моя точка зрения для примера: количество пар всегда будет больше за N. Для примера будут такие варианты: (1,2) (2,3) и (1,3), бо 3 друг друга 1
Как я понял, задачю надо решать на графы, но не знаю как.

Благадарен за любую помошь.
Спасибо.

(за русский извините, я ученик с Украины)

[Sazary]

Сразу оговорюсь, что с графами знаком плохо.
Вроде работает.

uses crt;
var
M,N,i,j,a,b : integer;
cnt : integer;
matr : array[1..5000,1..5000] of boolean;

procedure rec(ti : integer; ci : integer);
 var i : integer;
 begin
 { -- здесь была ненужная строчка -- }

 for i:=1 to N do
  if i=ti then continue
  else if i=ci then continue
  else
   begin
   if matr[ci,i]=true then
    begin
     if matr[ti,i] = false then
      begin
      matr[ti,i] := true;
      rec(ti,i);
      end;
    end;

   end;

 end;

begin
clrscr;
readln(M,N);
for i:=1 to N do
 for j:=1 to N do
  matr[i,j] := false;

for i:=1 to M do
 begin
 readln(a,b);
 matr[a,b] := true;
 end;
{--------}
cnt := 0;
for i:=1 to N do
 for j:=1 to N do
  if matr[i,j] = true then
   rec(i,j);
{--------}
for i:=1 to N do
 for j:=1 to N do
  if matr[i,j] = true then inc(cnt);
writeln(cnt);
readln;
end.

Проверил на:

2 3
1 2
2 3

Результат 3.
И на

4 5
1 2
2 4
4 3
3 5

Результат 10.

[Witaliy]

Очень большое спасибо, а как назыветься такой алгоритм?

[Witaliy]

Извините, моя ошыбка:
Например

3 2
1 2
2 3

[Sazary]

Сообщение от Witaliy

Очень большое спасибо, а как назыветься такой алгоритм?

Я не использовал готовый алгоритм (а если так и получилось, то это совпадение ).

Извините, моя ошыбка:
Например

3 2
1 2
2 3

Первое число в первой строке - M, второе - N.
Далее идут M строк (пары, о которых известно)
То, что вы сейчас привели, под эти критерии не подходит )

----
Если нужно, могу описать логику работы (вроде как, там и так все понятно, но, может быть, это только для меня ))

[Witaliy]

было б хорошо.

[Sazary]

Сначала читаем M (количество известных пар) и N (количество учеников).

readln(M,N);

Далее забиваем матрицу смежности нулями (т.к. каждый элемент может находиться только в одном состоянии (дружит/не дружит), то используем тип boolean), то есть false'ами.

for i:=1 to N do
 for j:=1 to N do
  matr[i,j] := false;

Потом считываем строки (пары) и пишем в матрицу:

for i:=1 to M do
 begin
 readln(a,b);
 matr[a,b] := true;
 end;

Число пар (общее) пока равно 0:

cnt := 0;

Далее запускаем цикл, который идет по строкам (то есть по каждому ученику):

for i:=1 to N do
 for j:=1 to N do
  if matr[i,j] = true then
   rec(i,j);

Вложенный цикл смотрит, дружит ли ученик j с учеником i. Если дружит, то нужно проверить с кем дружит ученик j. ДЛя этого вызываем процедуру rec(ti : integer; ci : integer).
ti - ученик, для которого мы ищем друзей (по принципу "друг моего друга - мой друг").
ci - текущий друг в цепочке.

Процедура:

Запускаем цикл, который обходит всех учеников:

for i:=1 to N do

Если наткнулись на исходного ученика - пропускаем:

if i=ti then continue

Если на себя (текущего) - тоже:

else if i=ci then continue

иначе:
Если текущий (в этом цикле) ученик дружит с текущим (из вне) другом исходного ученика:

if matr[ci,i]=true then

и если он еще не дружит с исходным учеником (ti):

if matr[ti,i] = false then

то отмечаем дружбу:

matr[ti,i] := true;

и рекурсивно вызываем себя, уже относительно нового текущего друга (исходный ученик тот же):

rec(ti,i);

----------
Когда обошли всех и вся, возвращаемся в программу. Там уже обходим всех учеников и по матрице смежности смотрим кто с кем дружит (и плюсуем cnt):

for i:=1 to N do
 for j:=1 to N do
  if matr[i,j] = true then inc(cnt);

Очень надеюсь, что понятно объяснил )