-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathFind the Weak Connected Component in the Directed Graph
83 lines (75 loc) · 2.7 KB
/
Find the Weak Connected Component in the Directed Graph
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
* Definition for Directed graph.
* class DirectedGraphNode {
* int label;
* ArrayList<DirectedGraphNode> neighbors;
* DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
* };
*/
public class Solution {
/**
* @param nodes a array of Directed graph node
* @return a connected set of a directed graph
*/
public class Node {
public int label;
public HashSet<Node> neighbors;
public Node(DirectedGraphNode parent) {
this.label = parent.label;
neighbors = new HashSet<Node>();
}
}
public List<Node> deepCopy(ArrayList<DirectedGraphNode> nodes) {
List<Node> copy = new ArrayList<>();
HashMap<DirectedGraphNode, Node> map = new HashMap<>();
//copy node's label and put in map, put in copy list
for (int i = 0; i < nodes.size(); i++) {
Node n = new Node(nodes.get(i));
map.put(nodes.get(i), n);
copy.add(n);
}
//copy node's neighbors and put node to neighbors list
for (int i = 0; i < nodes.size(); i++) {
DirectedGraphNode node = nodes.get(i);
Node n = map.get(node);
for (DirectedGraphNode neighbor : node.neighbors) {
Node nn = map.get(neighbor);
if (!n.neighbors.contains(nn)) {
n.neighbors.add(nn);
}
if (!nn.neighbors.contains(n)) {
nn.neighbors.add(n);
}
}
}
return copy;
}
public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
if (nodes == null || nodes.size() == 0) {
return new ArrayList<List<Integer>>();
}
List<Node> list = deepCopy(nodes);
List<List<Integer>> result = new ArrayList<>();
HashMap<Node, Boolean> visited = new HashMap<>();
// dfs and add the list to result
for (Node node : list) {
if (!visited.containsKey(node)) {
List<Integer> group = new ArrayList<>();
visit(node, visited, group);
Collections.sort(group);
result.add(group);
}
}
return result;
}
// dfs visit each undirected node, and add the component to the list
public void visit(Node node, HashMap<Node, Boolean> visited, List<Integer> group) {
visited.put(node, true);
for (Node neighbor : node.neighbors) {
if (!visited.containsKey(neighbor)) {
visit(neighbor, visited, group);
}
}
group.add(node.label);
}
}