请找出有向图中弱连通分量。图中的每个节点包含 1 个标签和1 个相邻节点列表。（有向图的弱连通分量是任意两点均有有向边相连的极大子图）
将连通分量内的元素升序排列。
图模型说明:
Graph
For example:
{1,2,4#2,1,4#3,5#4,1,2#5,3} represents follow graph:
------
\ | |
\ | |
\ | |
\ | |
we use # to split each node information.
1,2,4 represents that 2, 4 are 1's neighbors
2,1,4 represents that 1, 4 are 2's neighbors
3,5 represents that 5 is 3's neighbor
4,1,2 represents that 1, 2 are 4's neighbors
5,3 represents that 3 is 5's neighbor
样例 1:
输入: {,,#,#,###,}
输出: [[,,],[,,]]
解释:
-----> -->
\ | ^
\ | |
\ |
\ v
->
样例 2:
输入: {,#,#,}
输出: [[,,]]
【题解】
算法：并查集
并查集是一种可以动态维护若干个不重叠的集合，并支持合并与查询两种操作的一种数据结构
一般我们建立一个数组fa或者用map表示一个并查集，fa[i]表示i的父节点。
- 初始化：每一个点都是一个集合，因此自己的父节点就是自己fa[i]=i
- 查询：每一个节点不断寻找自己的父节点，若此时自己的父节点就是自己，那么该点为集合的根结点，返回该点。
- 修改：合并两个集合只需要合并两个集合的根结点，即fa[RootA]=RootB，其中RootA,RootB是两个元素的根结点。
- 路径压缩：实际上，我们在查询过程中只关心根结点是什么，并不关心这棵树的形态(有一些题除外)。因此我们可以在查询操作的时候将访问过的每个点都指向树根，这样的方法叫做路径压缩，单次操作复杂度为O(logn),经过路径压缩后可将查询时间优化到O(1)
我们用um作为father数组维护点之间的关系，通过并查集连通块,将有向连接转换为无向连接
思路
对于图上上两个点，只要他们有连边关系，那么他们就属于同一个弱连通分量
于是这道题我们就可以转换为无向图找联通块
算法流程
- 遍历图上节点，对于有连边关系的两个点，通过并查集将他们合并为一个合集
- 遍历并查集中的每一个点，找到其父亲，再加入父亲所在的 List 中
- 将所有 List 按照点从小到大排序输出
复杂度分析
- 时间复杂度
O(n) - 并查集的复杂度
- 空间复杂度
O(n) - 需要用一个map去记录点与点之间的关系
public class Solution {
/*
* @param nodes: a array of Directed graph node
* @return: a connected set of a directed graph
*/
private Map<Integer, Integer> um=null;
public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
um = new HashMap<>();
for (DirectedGraphNode node : nodes) {//将所有连通点用并查集建立图
find(node.label);
for (DirectedGraphNode neighbor : node.neighbors) {
connect(node.label, neighbor.label);
}
}
Map<Integer, List<Integer>> hash = new HashMap<>();
for (Integer roots : um.keySet()) {//查找每个节点所属的块
int father = find(roots);
if (!hash.containsKey(father)) {
hash.put(father, new ArrayList<>());
}
List<Integer> list = hash.get(father);
list.add(roots);
Collections.sort(list);
}
return new ArrayList<>(hash.values());
}
private int find (int x) {//查询函数
if (!um.containsKey(x)) {
um.put(x,x);
}
int father = um.get(x);
if (father == x) {
return x;
}
father = find(father);
um.put(x, father);
return father;
}
private void connect(int a, int b) {//合并函数
int roota = find(a),rootb=find(b);
if (roota != rootb) {
um.put(Math.min(roota, rootb), Math.max(roota, rootb));
}
}
}