Решение задачи №150 «Друзья» с ACMP

Условие задачи

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

Входные данные
В первой строке входного файла INPUT.TXT заданы два числа: N и S (1 ≤ N ≤ 100; 1 ≤ S ≤ N), где N - количество человек в клубе, а S – номер конкретного человека. В следующих N строках записано по N чисел - матрица смежности, состоящая из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что люди с номерами i и j – друзья, а 0 – выражает неопределенность.

Выходные данные
В выходной файл OUTPUT.TXT выведите количество гарантированных друзей у человека с номером S, помня о транзитивности дружбы.

Решение на C++


    #include<iostream> 

using namespace std; 

int a[100][100],b[100],k,n; 

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(){ 

int s,i,j; 

	cin>>n>>s;s--; 

	for(i=0;i<n;++i) 

		for(j=0;j<n;j++)cin>>a[i][j]; 

	b[s]=1;

	for(j=0;j<n;++j) 

		if(a[s][j])dfs(j); 

	cout<<k; 

return 0;}

Условия задач взяты с сайта acmp.ru