LeetCode Evaluate Division(并查集)

    技术2022-07-11  83

    问题:给出一些形式为a/b=c的等式,要求一系列x/y的值

    思路:

    当a/b=c时,用p[a]=b,w[a]=c,表示a父结点为b,并且从a到b的权值为c.假设a的根结点为c,a到c的权值为w1,d的根结点为f,d到f的权值为w2,而a/d的值为w,合并时,c到f的权值为w*w2/w1

     具体代码参考:

    https://github.com/wuli2496/OJ/tree/master/LeetCode/Evaluate Division

    Processed: 0.013, SQL: 9