Problem is here: Graph Valid Tree
Before entering the problem solving process, we need to consider some important facts about the tree:
- A tree with n nodes must have exactly
n - 1edges - There is no cycle in the tree
- The whole tree has to be a complete connected graph (there is always a path to go from a node
ato nodeb)
One more important thing is that we will utilize the concept used in Kahn's algorithm to solve this. By calculating the degrees of the nodes, we can eventually remove the nodes while maintaining the shape and checking the cycle in the graph.
So if there is a cycle in the tree, at some point, the node with the lowest degree will have the value larger than 1.
So here is the algorithm:
Algorithm:
- Go through the edges in the tree, increase the degree of the node
- Keep track a map of adjacent nodes to a specific nodes
- Find the node with the smallest degree, if that node does not have a degree <= 1, return false since there is a cycle
- else: for each adjacent node to that node, decrease the degree of that adjacent node by 1
- repeat the process untill all node has a degree of 0 and are all visited
- how to keep track of a set of node? store the nodes in set and see if which one can be considered
here is the code
class Solution {
public boolean validTree(int n, int[][] edges) {
int[] degree = new int[n];
Set<Integer> notVisited = new HashSet<>();
Map<Integer, Set<Integer>> map = new HashMap<>();
if (edges.length < n - 1) {
return false;
}
for (int[] edge: edges) {
int node1 = edge[0];
int node2 = edge[1];
degree[node1] ++;
degree[node2]++;
notVisited.add(node1);
notVisited.add(node2);
// add to the map
map.putIfAbsent(node1, new HashSet<>());
map.putIfAbsent(node2, new HashSet<>());
map.get(node1).add(node2);
map.get(node2).add(node1);
// union find and make sure they all have the same parents?
}
// System.out.println(Arrays.toString(degree));
while (!notVisited.isEmpty()) {
// find the node with the lowest degree
int nodeLowestDegree = Integer.MAX_VALUE;
for (int node: notVisited) {
if (nodeLowestDegree == Integer.MAX_VALUE) {
nodeLowestDegree = node;
} else {
if (degree[node] < degree[nodeLowestDegree]) {
nodeLowestDegree = node;
}
}
}
if (degree[nodeLowestDegree] > 1 || (degree[nodeLowestDegree] == 0 && notVisited.size() > 1)) {
return false;
}
// remove it and adjust the adjacent nodes' degree
notVisited.remove(nodeLowestDegree);
// update adjacent nodes
for (int adjNode: map.get(nodeLowestDegree)) {
degree[adjNode] --;
}
}
return true;
}
}
Top comments (0)