Friend Circle Queries

  • + 0 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
    

    }