Buttercola: Zenefits: Validate a Directed Graph Tree
Understand the problem:If the graph is undirected graph, it would be the same as the Leetcode question : Graph Valid Tree.
http://buttercola.blogspot.com/2015/08/leetcode-graph-valid-tree.html
The corner case which need to be very careful is if the graph contains more than one connected components, i.e. multiple islands. In this case, the graph is not a valid tree because a tree can have one and only one root.
The same role applies to the directed graph. For a directed graph, we can do a topological sorting. If a valid topological sorting exists, it means the graph does not contain a circle.
But how to deal with multiple connected components?
One solution is to calculate the in-degree for each node. For a valid tree, there should be one and only one node with in-degree 0. If not, e.g. there are two nodes with in-degree 0, the graph must not be a valid tree. Then we can also do a topological sort from this root node, avoiding starting from each and every node.
Read full article from Buttercola: Zenefits: Validate a Directed Graph Tree
Understand the problem:If the graph is undirected graph, it would be the same as the Leetcode question : Graph Valid Tree.
http://buttercola.blogspot.com/2015/08/leetcode-graph-valid-tree.html
The corner case which need to be very careful is if the graph contains more than one connected components, i.e. multiple islands. In this case, the graph is not a valid tree because a tree can have one and only one root.
The same role applies to the directed graph. For a directed graph, we can do a topological sorting. If a valid topological sorting exists, it means the graph does not contain a circle.
But how to deal with multiple connected components?
One solution is to calculate the in-degree for each node. For a valid tree, there should be one and only one node with in-degree 0. If not, e.g. there are two nodes with in-degree 0, the graph must not be a valid tree. Then we can also do a topological sort from this root node, avoiding starting from each and every node.
public
static
boolean
validTree(
int
n,
int
[][] edges) {
if
(n <=
0
|| edges ==
null
|| edges.length ==
0
) {
return
false
;
}
// Step 1: calculate the in-degree for each vertex, to find out the root of the tree
Map<Integer, Integer> inDegree =
new
HashMap<>();
for
(
int
[] edge: edges) {
if
(!inDegree.containsKey(edge[
1
])) {
inDegree.put(edge[
1
],
1
);
}
else
{
int
val = inDegree.get(edge[
1
]);
inDegree.put(edge[
1
], val +
1
);
}
}
// Iterate the inDegree and check 0 degree vertex
int
root =
0
;
int
count =
0
;
for
(
int
i =
0
; i < n; i++) {
if
(!inDegree.containsKey(i)) {
root = i;
count++;
}
}
if
(count !=
1
) {
return
false
;
}
// Step 2: transform the edge list to the adjlist
Map<Integer, List<Integer>> adjList =
new
HashMap<>();
for
(
int
[] edge : edges) {
if
(adjList.containsKey(edge[
0
])) {
List<Integer> neighbors = adjList.get(edge[
0
]);
neighbors.add(edge[
1
]);
}
else
{
List<Integer> neighbors =
new
ArrayList<>();
neighbors.add(edge[
1
]);
adjList.put(edge[
0
], neighbors);
}
}
boolean
[] visited =
new
boolean
[n];
return
validTreeHelper(root, visited, adjList);
}
private
static
boolean
validTreeHelper(
int
vertexId,
boolean
[] visited, Map<Integer, List<Integer>> adjList) {
if
(visited[vertexId]) {
return
false
;
}
visited[vertexId] =
true
;
List<Integer> neighbors = adjList.get(vertexId);
if
(neighbors !=
null
) {
for
(
int
neighbor : neighbors) {
if
(!validTreeHelper(neighbor, visited, adjList)) {
return
false
;
}
}
}
visited[vertexId] =
false
;
return
true
;
}
public
static
void
main(String[] args) {
Scanner scanner =
new
Scanner(System.in);
int
numVertices = scanner.nextInt();
int
numEdges = scanner.nextInt();
int
[][] edges =
new
int
[numEdges][
2
];
for
(
int
i =
0
; i < numEdges; i++) {
edges[i][
0
] = scanner.nextInt();
edges[i][
1
] = scanner.nextInt();
}
boolean
result = Solution.validTree(numVertices, edges);
System.out.println(result);
scanner.close();
}