You are viewing a single comment's thread. Return to all comments →
javascript union-find, using Map instead of Array. easy to understand:
function maxCircle(queries) {
let parentMap = new Map() let sizeMap = new Map() let maxGroup = 1 function find(p){ if(parentMap.has(p)){ while(p!==parentMap.get(p)){ parentMap.set(p, parentMap.get(parentMap.get(p))) p = parentMap.get(p) } }else{ parentMap.set(p, p) } return p } function union(p, q){ let rootP = find(p) let rootQ = find(q) if(!sizeMap.has(rootP)){ sizeMap.set(rootP, 1) } if(!sizeMap.has(rootQ)){ sizeMap.set(rootQ, 1) } if(rootP===rootQ){ return maxGroup } let groupSize = sizeMap.get(rootP)+sizeMap.get(rootQ) if(sizeMap.get(rootP)<sizeMap.get(rootQ)){ parentMap.set(rootP, rootQ) sizeMap.set(rootQ, groupSize) }else{ parentMap.set(rootQ, rootP) sizeMap.set(rootP, groupSize) } maxGroup = Math.max(maxGroup, groupSize) return maxGroup } let res = [] for(let [p,q] of queries){ res.push(union(p,q)) } return res
}
Seems like cookies are disabled on this browser, please enable them to open this website
Friend Circle Queries
You are viewing a single comment's thread. Return to all comments →
javascript union-find, using Map instead of Array. easy to understand:
function maxCircle(queries) {
}