LeetCode C++ 两种方法使用dfs求解朋友圈的个数（最大联通分量的个数？）

 方法一

int findCircleNum(vector<vector<int>>& M) {

	int n = M.size();
	vector<vector<int>> map_n(n);
	vector<bool> visit(n, false);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
		{
			if (M[i][j] == 1 and i != j)
				map_n[i].push_back(j);
		}
	}
	int result = 0;
	for (int i = 0; i < n; i++)
	{
		if (visit[i] == false)
		{
			result += 1;
			visit[i] = true;
			dfs(M, visit, i);
		}
	}

	return result;
			
}

void dfs(vector<vector<int>> &M, vector<bool> &visit, int index)
{
	int n = M.size();
	for (int i = 0; i < n; i++)
	{
		//if(find(map_n[i].begin(),map_n[i].end(),index) != map_n[i].end())
		if (M[index][i] == 1 and visit[i] == false)
		{
			visit[i] = true;
			dfs(M, visit, i);
		}
	}
}

 

 

方法二、使用邻接矩阵

void dfs(vector<vector<int>> &map_n, vector<bool> &visit, int index)
{
	int n = map_n[index].size();
	for (int i = 0; i < n; i++)
	{
		if (visit[map_n[index][i]] == false)
		{
			visit[map_n[index][i]] = true;
			dfs(map_n,visit, map_n[index][i]);
		}
	}


	//int n = M.size()
	//for (int i = 0; i < n; i++)
	//{
	//	//if(find(map_n[i].begin(),map_n[i].end(),index) != map_n[i].end())
	//	if (M[index][i] == 1 and visit[i] == false)
	//	{
	//		visit[i] = true;
	//		dfs(M, visit, i);
	//	}
	//}
}
int findCircleNum(vector<vector<int>>& M) {

	int n = M.size();
	vector<vector<int>> map_n(n);
	vector<bool> visit(n, false);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
		{
			if (M[i][j] == 1 and i != j)
				map_n[i].push_back(j);
		}
	}
	int result = 0;
	for (int i = 0; i < n; i++)
	{
		if (visit[i] == false)
		{
			result += 1;
			visit[i] = true;
			dfs(map_n, visit, i);
		}
	}

	return result;
			
}