写在前面
- 第一次遇到这个问题，对于未能现场bug-free通过耿耿于怀，遂将此题记录下来，尝试使用多种方法解决该问题。
题目描述
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有传递性：如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。之后返回全部学生朋友圈的数目，类型为整型。
- 示例1:
输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明：已知学生0和学生1互为朋友，他们在一个朋友圈；第2个学生自己在一个朋友圈。所以返回2。
- 示例2:
输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
问题分析
本题可用多种方法解决——dfs, bfs, 图，并查集。扎实的基础才是解决问题的核心所在哇。
解决思路
广度优先搜索(bfs)
- 广度优先搜索(BFS，Breadth First Search)，其过程是对每一层节点依次访问，访问完一层进入下一层，而且每个节点只能访问一次。
- 广度优先遍历树，需要用到队列（Queue）来存储节点对象,队列的特点就是先进先出。
代码如下：
int findCircleNum(vector<vector<int>> &nums) {
//定义visited数组，用来存储bfs顶部元素
vector<int> visited(nums.size()) = {0};
int count = 0;//计数值，用于返回该结果
queue<int> queue;//bfs快乐队列
for (int i = 0; i < nums.size(); i++) {
if (visited[i] == 0) {
queue.push_back(i);
while (!queue.empty()) {
int s = queue.pop_back();
visited[s] = 1;
for (int j = 0; j < nums.length; j++) {
if (nums[s][j] == 1 && visited[j] == 0)
queue.push_back(j);
}
}
count++;
}
}
return count;
}
深度优先搜索(dfs)
遍历二维数组的所有元素，对于每个元素，如果该元素尚未被访问过，则从该元素开始深度优先搜索，通过矩阵isConnected得到该元素组成朋友的元素有哪些，这些元素和该元素属于同一个朋友圈，然后对这些元素继续dfs，直到同一个连通分量的所有元素都被访问到，即可得到一个计数值。遍历完全部元素以后，即可得到连通分量的总数，即朋友圈的总数。
代码1：
//查找和第i个人为同一朋友圈的人
void dfs(vector<vector<int>>& nums,int i, vector<bool>& visited)
{
visited[i] = true;
for(int j = 0; j < nums.size(); j++)
{
if(nums[i][j] == 0 || visited[j] == true) continue; //这句话是关键
dfs(nums, j, visited); //向前递归查找
}
}
int findCircleNum (vector<vector<int>>& nums) {
int n = nums.size();
if(n == 0) return 0;
int res = 0;
vector<bool> visited(n, false); //这个人是否被归入某一朋友圈
for(int i = 0; i < n; i++)
{
if(visited[i] == true) continue;
dfs(nums, i, visited);
res++;
}
return res;
}
代码2
//先定义dfs函数，变量为原二维数组，遍历所需一维数组，朋友圈中的元素总数和行数i
void dfs(vector<vector<int>>& isConnected, vector<int>& visited, int elements, int i) {
visited[i] = true; //标记遍历过的数组下标为true
//纵向遍历
for (int j = 0; j < elements; j++) {
//如果当前位置为1，而它的对称列并未被遍历，则将那一列置1
if (isConnected[i][j] == 1 && !visited[j]) {
visited[j] = 1;
dfs(isConnected, visited, elements, j);
}
}
}
int findCircleNum(vector<vector<int>>& isConnected) {
int elements = isConnected.size();//定义行数
vector<int> visited(elements);//遍历判断所需一维数组
int cnt = 0;
//横向遍历。如果该行未遍历过，就开始dfs
for (int i = 0; i < elements; i++) {
if (!visited[i]) {
dfs(isConnected, visited, elements, i);
cnt++;
}
}
return cnt;
}
并查集思想
并查集是判断元素是否在统一集合中的数据结构。 最开始，每个元素都在一个单独的集合里，集合的顶点就是自己；当有相同集合的元素合并之后，他们就在同一集合里，且元素值相等。
- 并查集的缺点：如果发生不恰当的合并动作，可能造成查询时间过长的结果(因为需要遍历集合)。
代码如下：
int arr[10000];
int cnt = 0;
void init() {
for(int i = 0; i < 10000; i++) {
arr[i] = i; //先把集合元素初始化为它的下标，表明它在单独的集合里
}
//定义一个查询函数，返回它所在集合的顶点元素
int get(int x) {
if(x == arr[x]) return x; //如果下标x的值就是当前下标，表明它已经是顶点元素了，返回即可
arr[x] = get(arr[x]); //一个简单的递归，往上寻找顶点元素
return arr[x];
}
//定义一个合并函数，
void merge(int x, int y) {
arr[get(x)] = get(y);
}
int findFriendCircle(vector<vector<int>> &nums) {
init();
for(int i = 0; i < nums.size(); i++) {
for(int j = 0; j < nums[0].size(); j++) {
//如果下标为i,j的元素值为1，那么i和j就属于同一朋友圈
if(nums[i][j] == 1) {
merge(i, j); //把i和j合并起来
}
}
}
//然后遍历这个并查集的集合
for(int i = 0; i < nums.size(); i++) {
//如果这个元素等于它自己，那他自己就是单独的一个朋友圈，cnt++就可
if(arr[i] == i) {
cnt++;
}
}
return cnt;
}
}
