题解 | 爱丽丝的人偶依赖协议

const rl = require("readline").createInterface({ input: process.stdin });
const ipt = [];
rl.on('line',line=>{
    ipt.push(line);
}).on('close',()=>{
    const n1 = parseInt(ipt[0]);
    const msgs1 = [];
    for(let i = 0;i<n1;i++){
        msgs1.push(ipt[1+i].trim().split(',').map(Number));
    }
    const n2 = parseInt(ipt[n1+1]);
    const msgs2 = [];
    for(let i = 0;i<n2;i++){
        msgs2.push(ipt[n1+2+i].trim().split(',').map(Number));
    }
    // console.log(n1,msgs1,n2,msgs2);
    solve(n1,msgs1);
    solve(n2,msgs2);
})
function solve(n,msgs){
    // const parent = new Map();
    const inDegs = new Map();
    const graph = new Map();
    const vers = new Map();
    for(let msg of msgs){
        const [u,v,ver] = msg;
        if(!inDegs.has(u)){
            inDegs.set(u,0);
        }
        if(!inDegs.has(v)){
            inDegs.set(v,0);
        }
        if(!graph.has(v)){
            graph.set(v,[]);
        }
        graph.get(v).push(u);
        if(!vers.has(v) || ver>vers.get(v)){
            vers.set(v,ver);
        }
        inDegs.set(u,inDegs.get(u)+1);
    }
    const queue = [];
    for(let key of inDegs.keys()){
        if(inDegs.get(key) === 0){
            queue.push(key);
        }
    }
    while(queue.length){
        const key = queue.shift();
        let nexts = graph.get(key) || [];
        for(let next of nexts){
            inDegs.set(next,inDegs.get(next)-1);
            if(inDegs.get(next) === 0){
                queue.push(next);
            }
        }
    }
    // console.log(inDegs);
    for(let key of inDegs.keys()){
        if(inDegs.get(key) !== 0){
            console.log(false);
            return;
        }
    }
    for(let msg of msgs){
        const [u,v,ver] = msg;
        if(ver<vers.get(v)){
            msg[2] = vers.get(v);
        }
    }
    msgs.forEach((val,idx)=>{
        console.log(val.join(','));
    })
    // function union(node1,node2,parent){
    //     parent.set(find(node2,parent),find(node1,parent));
    // }
    // function find(node,parent){
    //     if(!parent.has(node)){
    //         parent.set(node,node);
    //     }
    //     if(parent.get(node) !== node){
    //         parent.set(node,find(parent.get(node),parent));
    //     }
    //     return parent.get(node);
    // }
}