[OD E 100] 服务器广播需要广播的服务器数量

题目

题目描述
服务器连接方式包括直接相连，间接连接。
A和B直接连接，B和C直接连接，则A和C间接连接。
直接连接和间接连接都可以发送广播。
给出一个N*N数组，代表N个服务器，
matrix[i][j] == 1，则代表i和j直接连接；不等于 1 时，代表i和j不直接连接。
matrix[i][i] == 1，即自己和自己直接连接。matrix[i][j] == matrix[j][i]。
计算初始需要给几台服务器广播， 才可以使每个服务器都收到广播。

输入描述
输入为N行，每行有N个数字，为0或1，由空格分隔，

构成N*N的数组，N的范围为 1 <= N <= 40

输出描述
输出一个数字，为需要广播的服务器的数量

示例1
输入

1 0 0
0 1 0
0 0 1

输出

3

说明

3 台服务器互不连接，所以需要分别广播这 3 台服务器

示例2
输入

1 1
1 1

输出

1

说明

2 台服务器相互连接，所以只需要广播其中一台服务器

代码

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

void dfs(vector<vector<int>>& matr, vector<bool>& visited, int x, int n)
{

	visited[x] = true;

	for (int i = 0; i < n; i++)
	{
		if (matr[x][i] == 1 && !visited[i])
		{
			dfs(matr, visited, i, n);
		}
	}
}

int main()
{
	vector<vector<int>> matr;
	string sLine;
	while (getline(cin, sLine))
	{
		istringstream iss(sLine);
		vector<int> row;
		int val;
		while (iss >> val)
		{
			row.push_back(val);
		}
		matr.push_back(move(row));
	}

	int n = matr.size();
	vector<bool> visited(n, false);
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		if (!visited[i])
		{
			dfs(matr, visited, i, n);
			ans++;
		}
	}

	cout << ans;

	return 0;
}