Друзья

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

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

  //обход в глубину графа из вершины 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);

[Обсуждение] [Все попытки] [Задача]