图论(dfs深搜系列)9.23

类型一:dfs寻找独立连通块

一、统计无向图中无法互相到达的点的对数

给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。

思路：

首先找到独立的连通块以及该块中点的个数，一个连通块中的点和其他连通块都是无法互相到达的。所以假设一个连通块的点为x，一共的点为n；x*(n-x)/2。就是无法相互到达的点的对数

1.找到独立的连通块以及块中的个数。

如何找到独立的连通块，每次for循环，进去dfs函数，一连串的就是一个独立的连通块。

所以只需要在dfs中添加一个 记录块中的个数即可。

代码：

class Solution {boolean[] visited;public long countPairs(int n, int[][] edges) {//计算出每一个连通块中的个数就OKint size=edges.length;visited=new boolean[n];List<List<Integer>> links=new ArrayList<>();for(int i=0;i<n;i++)links.add(new ArrayList<>());for(int i=0;i<size;i++){links.get(edges[i][0]).add(edges[i][1]);links.get(edges[i][1]).add(edges[i][0]);}//计算无法相互到达的点数long res=0;for(int i=0;i<n;i++){if(visited[i])continue;long cnt=dfs(i,links);res+=cnt*(n-cnt);}return res/2;}public long dfs(int current,List<List<Integer>> links){long count=1;visited[current]=true;for(int next:links.get(current)){if(!visited[next]){count+=dfs(next,links);}}return count;}
}

难度递增，数据结构上增加难度

二、两个城市间路径的最小分数

给你一个正整数 n ，表示总共有 n 个城市，城市从 1 到 n 编号。给你一个二维数组 roads ，其中 roads[i] = [ai, bi, distancei] 表示城市 ai 和 bi 之间有一条 双向 道路，道路距离为 distancei 。城市构成的图不一定是连通的。

两个城市之间一条路径的 分数 定义为这条路径中道路的 最小 距离。

城市 1 和城市 n 之间的所有路径的 最小 分数。

题意：

让求从城市1->n之间，所有路径的最小分数。注意：路径是可以折返的；并且题目保证从1->n之间一定有一条路。

思路：

所以这道题就让我们求，以1开始的连通块中边的最小分数。

但是难点在于，两边之间不仅仅是点的序号，还有之间的距离。

所以在使用数据结构定义邻接表的时候就要考虑清楚。

之前定义邻接表的时候是:List<List<Integer>> links;集合里面存放集合，第一个集合是所有点的邻接表；第二个集合是下标为i的点的表。但是这个长度是与下标为i的点相邻的点的个数

在这里我们要用::List<List<int[]>> 或者 List<int[]>[] 两种方式来定义。

代码：

class Solution {boolean[] visited;public int minScore(int n, int[][] roads) {//在一个数组里面放的集合，集合里元素的类型是int[]visited=new boolean[n+1];List<int[]>[] links=new ArrayList[n+1];for(int i=1;i<=n;i++)links[i]=new ArrayList<>();//初始化邻接表for(int[] road:roads){int x=road[0];int y=road[1];int distance=road[2];links[x].add(new int[]{y,distance});links[y].add(new int[]{x,distance});}return dfs(1,links);}public int dfs(int current,List<int[]>[] links){visited[current]=true;int min=Integer.MAX_VALUE;for(int[] arr:links[current]){min=Math.min(min,arr[1]);if(!visited[arr[0]]){min=Math.min(min,dfs(arr[0],links));}}return min;}
}

三、统计完全连通分量的数量

给你一个整数 n 。现有一个包含 n 个顶点的 无向 图，顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges 其中 edges[i] = [ai, bi] 表示顶点 ai 和 bi 之间存在一条 无向 边。

完全连通分量:每个点之间都有一条边相连；所以:点*(点-1)/2==边数

思路：

判断每个连通块中边和点的数目，只要!visited[next],dfs(next,links)。进去dfs函数之后，点就+1；

    public void dfs(int current,List<List<Integer>> links){visited[current]=true;data[0]++;}

在对下标为i的邻接表进行遍历的时候，有边就++；但是会多数一倍。

    public void dfs(int current,List<List<Integer>> links){visited[current]=true;data[0]++;for(int next:links.get(current)){data[1]++;if(!visited[next]){dfs(next,links);}}}

代码：

class Solution {boolean[] visited;int[] data;public int countCompleteComponents(int n, int[][] edges) {//对于每个连通分量 计算其中的节点数和边数List<List<Integer>> links=new ArrayList<>();visited=new boolean[n];//构建邻接表for(int i=0;i<n;i++)links.add(new ArrayList<>());for(int i=0;i<edges.length;i++){links.get(edges[i][0]).add(edges[i][1]);links.get(edges[i][1]).add(edges[i][0]);}data=new int[2];int res=0;for(int i=0;i<n;i++){if(!visited[i]){dfs(i,links);if(data[1]==data[0]*(data[0]-1))res++;}data[0]=0;data[1]=0;}return res;}public void dfs(int current,List<List<Integer>> links){visited[current]=true;data[0]++;for(int next:links.get(current)){data[1]++;if(!visited[next]){dfs(next,links);}}}
}