Repurpose BFS Topological Sort
BFS for Topological sort illustrate a kind of strategy to traverse level by level starting from the outer leaves. This strategy could be used to solve several seem to be hard problems.
Find Center of Tree / Find Minimum Height Tree
Example:
Givenn = 6,edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
return[3, 4]for the tree root of the minimum tree.
The crux of the problem is bite off the leaves round by round so that we could find the center of the tree. Using the center as tree root, we got the lowest possible height of a tree.
First, we need to change the edges info into a graph representation e.g. adjacency list.
for(int i=0; i< edges.length; i++) {
if(tree[edges[i][0]]==null)
tree[edges[i][0]] = new ArrayList<Integer>();
if(tree[edges[i][1]]==null)
tree[edges[i][1]] = new ArrayList<Integer>();
tree[edges[i][0]].add(edges[i][1]);
tree[edges[i][1]].add(edges[i][0]);
numNeighbors[edges[i][0]]++;
numNeighbors[edges[i][1]]++;
}
To execute the biting, we need to perform it round by round. Here use a technique of putting a Sentinel at the end of the queue to signal the finish of a round. The bitting of leaves have to be round by round, otherwise, it might bite too much and the produce the wrong answer for the case the center is of two vertices.
//sentinel for signal one round of bite
readyQueue.add(-1);
int leavesRemoved = 0;
while(readyQueue.size()>1) {
int leaf = readyQueue.poll();
if(leaf==-1) {
if(leavesRemoved>=n-2) break;
readyQueue.add(-1); continue;
}
leavesRemoved++;
if(tree[leaf]!=null) {
for(Integer w:tree[leaf]) {
numNeighbors[w]--;
if(numNeighbors[w]==1) readyQueue.add(w);
}
}
}
Full code:
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return Collections.singletonList(0);
List<Integer>[] tree = new List[n]; //Adj matrix for the graph
int[] numNeighbors = new int[n];
for(int i=0; i< edges.length; i++) {
if(tree[edges[i][0]]==null)
tree[edges[i][0]] = new ArrayList<Integer>();
if(tree[edges[i][1]]==null)
tree[edges[i][1]] = new ArrayList<Integer>();
tree[edges[i][0]].add(edges[i][1]);
tree[edges[i][1]].add(edges[i][0]);
numNeighbors[edges[i][0]]++;
numNeighbors[edges[i][1]]++;
}
Queue<Integer> readyQueue = new LinkedList<Integer>();
for(int i=0; i<n; i++) {
if(numNeighbors[i]==1) readyQueue.add(i);
}
if(n<=2) return new ArrayList(readyQueue);
//sentinel for signal one round of bite
readyQueue.add(-1);
int leavesRemoved = 0;
while(readyQueue.size()>1) {
int leaf = readyQueue.poll();
if(leaf==-1) {
if(leavesRemoved>=n-2) break;
readyQueue.add(-1); continue;
}
leavesRemoved++;
if(tree[leaf]!=null) {
for(Integer w:tree[leaf]) {
numNeighbors[w]--;
if(numNeighbors[w]==1) readyQueue.add(w);
}
}
}
return new ArrayList(readyQueue);
}
}
Example 2:
Check whether the original sequenceorgcan be uniquely reconstructed from the sequences inseqs. Theorgsequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. Reconstruction means building a shortest common supersequence of the sequences inseqs(i.e., a shortest sequence so that all sequences inseqsare subsequences of it). Determine whether there is only one sequence that can be reconstructed fromseqsand it is theorgsequence.
Input:
org: [1,2,3], seqs: [[1,2],[1,3]]
Output:
false
Explanation:
[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.
This is essentially means if we have a topological sort (topological sort is for the purpose of keep the sequence order of seqs) of all vertices, and if that topological sort is unique and equals to given org sequence.
- We need to use HashMap instead of normal array for graph and counting in-degree, because we don't know the possible vertex v range.
- Beware of the situation with cycle. (check if #printed vertex equals total vertices in graph)
class Solution {
public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
Map<Integer, Integer> indegree = new HashMap<>();
for(List<Integer> seq:seqs) {
if(seq.size()==1) {
if(!graph.containsKey(seq.get(0))) {
graph.put(seq.get(0), new HashSet<Integer>());
indegree.put(seq.get(0), 0);
}
} else {
for(int i=0; i<seq.size()-1; i++) {
if(!graph.containsKey(seq.get(i))) {
graph.put(seq.get(i), new HashSet<Integer>());
indegree.put(seq.get(i), 0);
}
if(!graph.containsKey(seq.get(i+1))) {
graph.put(seq.get(i+1), new HashSet<Integer>());
indegree.put(seq.get(i+1), 0);
}
if(graph.get(seq.get(i)).add(seq.get(i+1))) { //hashset return true means no duplicate
indegree.put(seq.get(i+1), indegree.get(seq.get(i+1)) + 1);
}
}
}
}
Queue<Integer> q = new LinkedList<Integer>();
for(Map.Entry<Integer, Integer> indegreeCount:indegree.entrySet()) {
if(indegreeCount.getValue()==0) {
q.add(indegreeCount.getKey());
}
}
int index=0;
while(!q.isEmpty()) {
if(q.size()>1) return false;
int v = q.poll();
if(index>org.length-1 || org[index]!=v) return false;
index++;
Set<Integer> childSet = graph.get(v);
for(Integer child: childSet) {
int childIndegree = indegree.get(child) - 1;
if(childIndegree == 0) q.add(child);
indegree.put(child, childIndegree);
}
}
return index==org.length && index==graph.size();
}
}