Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Друзья

(Время: 1 сек. Память: 16 Мб Сложность: 41%)

Задача может быть решена путем стандартного обхода графа в глубину. Пусть a[i][j] – матрица смежности, данные которой описаны во входных данных, а в массиве b[i] будем хранить 1, если i-й человек является другом и 0 иначе. Рекурсивная функция dfs(v) будет помечать v-го человека как друга (b[v]=1), и далее рассматривать всех его непомеченных друзей и вызывать себя с параметром этих друзей. В момент пометки друга будем увеличивать на единицу некоторый счетчик, значение которого и окажется в итоге ответом на поставленную задачу. Сложность такого алгоритма O(n2), т.к. согласно такому алгоритму не будет повторных вызовов для одной и той же вершины графа.

Алгоритмическая реализация вышеописанного:

  //обход в глубину графа из вершины v с пометкой этой вершины
  void dfs(v){
    k=k+1;      //увеличиваем счетчик
    b[v]=true;  //помечаем "друга"
    for i=1..n
      if(a[v][i]=1 and b[i]=false) dfs(i);
  }
  //чтение входных данных
  read(n,s);
  for i=1..n
    for j=1..n
      read(a[i][j]);
 
  k=-1;   //обнуление счетчика с учетом того, что самого себя считать другом не следует
  dfs(s);
  write(k);

[Все попытки] [Задача]


 
     
Югорский НИИ ИТ, Югорский ФМЛ