Решение задачи "Друзья" с Acmp

С пояснением   Просмотров: 12


В клубе N человек. Многие из них - друзья. Так же известно, что друзья друзей так же являются друзьями. Требуется выяснить, сколько всего друзей у конкретного человека в клубе.

Код

#include <bits/stdc++.h>
 
using namespace std;
int n, s;
int k = -1;
bool b[100];
int a[100][100];
void dfs(int j){
    if(b[j])
        return;
    b[j] = 1;
    k++;
    for(int i = 0; i < n; ++i)
    if(a[j][i])
        dfs(i);
}
 
int main()
{
    cin >> n >> s;
    for(int i = 0; i < n; ++i){
        for (int j = 0; j < n; ++j){
            cin >> a[i][j];
        }
    }
    s--;
    dfs(s);
    cout << k;
    return 0;
}

         

 Администратор Photo Автор: Администратор


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

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться