小美的朋友关系（美团春招机试） Python AC代码

这道题网上已经有标准的解法了，就是反向并查集，但是很少看到能真正A掉的Python代码（C++最容易A）。主要原因可以归于以下四个原因：

1、节点数目最大可以到1e9，因此并查集初始化父节点时，千万不要每个节点都去初始化，很容易超时或者爆掉内存，使用HashMap去解决，只去初始化关系中有的节点。

2、被删除的关系可能原本就不存在，反向查询时删除操作是并查集中的添加操作，因此这种不存在的关系需要避免被添加到并查集中，没有这个操作的话结果会错误。

3、由于某些节点在初始化关系中是不存在的，因此查询时也会出现查询节点不再HashMap中，这个需要单独写代码去单独判断因此会额外增加计算开销，我的做法是不去判断是否在HashMap中，直接使用 Try...catch，这样不在HashMap中的节点会引发索引异常，但程序不会被终止掉，在catch中去添加否认的结果就行，省掉一部分判断计算成本。

4、最后的结果打印，因为查询最大可以到1e5的数量级别，使用循环print结果，IO开销太大了，会超时，我的做法是直接把结果拼成一个字符串，然后一次print，大幅削减IO开销。

这道题使用Python需要很多细节处理才行。

import sys

inputs = []
for line in sys.stdin:
    inputs.append(line.split())

inputs = [list(map(lambda x: int(x), line)) for line in inputs]

n, m, q = inputs[0][0], inputs[0][1], inputs[0][2]
init_friendships = inputs[1:m + 1]
queries = inputs[m + 1:]

class UnionFind:
    def __init__(self):
        self.parents = {}
        for i in range(m):
            f = init_friendships[i]
            self.parents[f[0]] = f[0]
            self.parents[f[1]] = f[1]
    
    def find(self, i):
        if self.parents[i] != i:
            self.parents[i] = self.find(self.parents[i])

        return self.parents[i]

    def union(self, i, j):
        parent_i =  self.find(i)
        parent_j = self.find(j)

        self.parents[parent_i] = parent_j

friendships = set()
for ship in init_friendships:
    friendships.add(tuple(sorted(ship)))

for i in range(q):
    q_tmp = queries[i]
    if q_tmp[0] == 1:
        if tuple(sorted(q_tmp[1:])) not in friendships:
            queries[i] = None

for q in queries:
    if q is not None and q[0] == 1:
        friendships.discard(tuple(sorted(q[1:])))

union_find = UnionFind()
for ship in friendships:
    union_find.union(*ship)

res = []
for q in queries[::-1]:
    if q is not None:
        if q[0] == 1:
            union_find.union(q[1], q[2])
        else:
            try:
                res.append('Yes' if union_find.find(q[1]) == union_find.find(q[2]) else 'No')
            except BaseException:
                res.append('No')

# for r in res[::-1]:
#     print(r)

r = '\n'.join(res[::-1])
print(r)