s********t
发帖数: 142 | 1 A sparse matrix and find the connected components using multi threading
using all the cores.
execution time criteria 3 s => good, 2s =>great 700 ms => excellent | s********t
发帖数: 142 | 2 下面是单线程，而且图是adjacency list
public class Solution {
//5763 ms, method: bfs, 时间O(N + E)，空间O(N)。
public List> connectedSet(ArrayList
nodes) {
List> res = new ArrayList<>();
List path = new ArrayList<>();
Set visited = new HashSet<>();
for (UndirectedGraphNode node : nodes) {
if (!visited.contains(node)) {
path.clear();
Queue queue = new LinkedList<>();
queue.offer(node);
visited.add(node);
path.add(node.label);
while (!queue.isEmpty()) {
UndirectedGraphNode p = queue.poll();
for (UndirectedGraphNode v : p.neighbors) {
if (!visited.contains(v)) {
visited.add(v);
queue.offer(v);
path.add(v.label);
}
}
}
Collections.sort(path);
res.add(new ArrayList(path));
}
}
return res;
}
//7451 ms, method: dfs, 时间O(N + E)，空间O(N)
public List> connectedSet2(ArrayList
nodes) {
List> res = new ArrayList<>();
List path = new ArrayList<>();
Set visited = new HashSet<>();
for (UndirectedGraphNode p : nodes) {
if (!visited.contains(p)) {
dfs(p, visited, path);
Collections.sort(path);
res.add(new ArrayList(path));
path.clear();
}
}
return res;
}
private void dfs(UndirectedGraphNode p, Set visited
, List path) {
visited.add(p);
path.add(p.label);
for (UndirectedGraphNode v : p.neighbors) {
if (!visited.contains(v))
dfs(v, visited, path);
}
}
} | s********t
发帖数: 142 | |
|
