描述
找出無(wú)向圖中所有的連通塊乎完。
圖中的每個(gè)節(jié)點(diǎn)包含一個(gè)label屬性和一個(gè)鄰接點(diǎn)的列表。（一個(gè)無(wú)向圖的?連通塊是一個(gè)子圖品洛，其中任意兩個(gè)頂點(diǎn)通過(guò)路徑相連树姨，且不與整個(gè)圖中的其它頂點(diǎn)相連。）
注意事項(xiàng)
每個(gè)連通塊內(nèi)部應(yīng)該按照l(shuí)abel屬性排序
說(shuō)明
Learn more about representation of graphs
樣例
給定圖:
A------B C
\ | |
\ | |
\ | |
\ | |
D E
返回 {A,B,D}, {C,E}桥状。其中有 2 個(gè)連通塊帽揪，即{A,B,D}, {C,E}
注意事項(xiàng)
每個(gè)連通塊內(nèi)部應(yīng)該按照l(shuí)abel屬性排序
思路
本題bfs的做法還是比較容易理解的，先給所有結(jié)點(diǎn)做一個(gè)false標(biāo)記辅斟，然后用for循環(huán)遍歷所有點(diǎn)標(biāo)記為false的點(diǎn)转晰，從一個(gè)點(diǎn)開始進(jìn)行bfs找到所有能找到的點(diǎn)，將找到的點(diǎn)標(biāo)記為true；結(jié)果加到數(shù)組排序
代碼
- bfs
/**
* Definition for Undirected graph.
* class UndirectedGraphNode {
* int label;
* ArrayList<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) {
* label = x;
* neighbors = new ArrayList<UndirectedGraphNode>();
*
* }
* }
*/
public class Solution {
/*
* @param nodes: a array of Undirected graph node
* @return: a connected set of a Undirected graph
*/
public List<List<Integer>> connectedSet(List<UndirectedGraphNode> nodes) {
List<List<Integer>> results = new ArrayList<>();
Map<UndirectedGraphNode, Boolean> visited = new HashMap<>();
if (nodes.size() == 0) {
return results;
}
for (int i = 0; i < nodes.size(); i++) {
visited.put(nodes.get(i), true);
}
for (int i = 0; i < nodes.size(); i++) {
UndirectedGraphNode node = nodes.get(i);
if (visited.get(node) == true) {
bfs(node, visited, results);
}
}
return results;
}
private void bfs(UndirectedGraphNode node,
Map<UndirectedGraphNode, Boolean> visited,
List<List<Integer>> results) {
Queue<UndirectedGraphNode> queue = new LinkedList<>();
List<Integer> level = new ArrayList<>();
queue.offer(node);
visited.put(node, false);
while (!queue.isEmpty()) {
UndirectedGraphNode head = queue.poll();
level.add(head.label);
for (UndirectedGraphNode neighbor : head.neighbors) {
if (visited.get(neighbor) == true) {
queue.offer(neighbor);
visited.put(neighbor, false);
}
}
}
Collections.sort(level);
results.add(level);
}
}
- 并查集
public
class Solution {
class UnionFind {
HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
UnionFind(HashSet<Integer> hashSet)
{
for (Integer now : hashSet) {
father.put(now, now);
}
}
int find(int x)
{
int parent = father.get(x);
while (parent != father.get(parent)) {
parent = father.get(parent);
}
return parent;
}
int compressed_find(int x)
{
int parent = father.get(x);
while (parent != father.get(parent)) {
parent = father.get(parent);
}
int next;
while (x != father.get(x)) {
next = father.get(x);
father.put(x, parent);
x = next;
}
return parent;
}
void union(int x, int y)
{
int fa_x = find(x);
int fa_y = find(y);
if (fa_x != fa_y)
father.put(fa_x, fa_y);
}
}
List<List<Integer> > print(HashSet<Integer> hashSet, UnionFind uf, int n) {
List<List<Integer> > ans = new ArrayList<List<Integer> >();
HashMap<Integer, List<Integer> > hashMap = new HashMap<Integer, List<Integer> >();
for (int i : hashSet) {
int fa = uf.find(i);
if (!hashMap.containsKey(fa)) {
hashMap.put(fa, new ArrayList<Integer>());
}
List<Integer> now = hashMap.get(fa);
now.add(i);
hashMap.put(fa, now);
}
for (List<Integer> now : hashMap.values()) {
Collections.sort(now);
ans.add(now);
}
return ans;
}
public
List<List<Integer> > connectedSet(ArrayList<UndirectedGraphNode> nodes)
{
// Write your code here
HashSet<Integer> hashSet = new HashSet<Integer>();
for (UndirectedGraphNode now : nodes) {
hashSet.add(now.label);
for (UndirectedGraphNode neighbour : now.neighbors) {
hashSet.add(neighbour.label);
}
}
UnionFind uf = new UnionFind(hashSet);
for (UndirectedGraphNode now : nodes) {
for (UndirectedGraphNode neighbour : now.neighbors) {
int fnow = uf.find(now.label);
int fneighbour = uf.find(neighbour.label);
if (fnow != fneighbour) {
uf.union(now.label, neighbour.label);
}
}
}
return print(hashSet, uf, nodes.size());
}
}