Merging Communities

  • + 0 comments

    Js

    function processData(input) {
        let inputs = input.split('\n');
        let n = parseInt(inputs.shift())
        const arrUnion = Array.from({ length: n + 1 }, (_, i) => i)
        const arrSize = Array(n + 1).fill(1);
        
        for (const query of inputs) {
            let command = query.split(' ')[0];
            let number1 = parseInt(query.split(' ')[1]);
            let number2 = parseInt(query.split(' ')[2]);
            if (command === 'Q') {
                let node = number1;
                while (arrUnion[node] !== node) {
                    node = arrUnion[arrUnion[node]]
                }
                console.log(arrSize[node]);
            } else if (command === 'M') {
                if (number1 === number2) {
                    continue;
                }
                let node1 = number1;
                let node2 = number2;
                while (arrUnion[node1] !== node1) {
                    node1 = arrUnion[arrUnion[node1]]
                }
                while (arrUnion[node2] !== node2) {
                    node2 = arrUnion[arrUnion[node2]]
                }
                if (node1 === node2) {
                    continue;
                }
                let [big, small] = arrSize[node1] >= arrSize[node2] ? [node1, node2] : [node2, node1];
                arrUnion[small] = big;
                arrSize[big] += arrSize[small];
            }
        } 
    }