题目描述

blablabla

样例

N, K = map(int, input().split())


p = [i for i in range(N+1)]

d = [0 for i in range(N+1)]


def find(x):
    if p[x] != x:
        temp = find(p[x])
        d[x] += d[p[x]]
        p[x] = temp
    return p[x]

if __name__ == "__main__":
    res = 0
    for k in range(K):
        line = list(map(int, input().split()))
        opt = line[0]
        x = line[1]
        y = line[2]

        if x > N or y > N:
            res += 1

        else:
            px = find(x)
            py = find(y)
            if opt == 1:
                if px == py and (d[x] - d[y]) % 3 != 0:
                    res += 1
                elif px != py:
                    p[px] = py
                    d[px] = d[y] - d[x]
            else:
                if px == py and (d[x] - d[y] - 1) % 3 != 0:
                    res += 1
                elif px != py:
                    p[px] = py
                    d[px] = d[y] + 1 - d[x]
    print(res)

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla