Very few orders of O (α (N)). α (n) is the reciprocal of the Ackermann function A (n, n).
He has created a very useful library. .. https://note.nkmk.me/python-union-find/ https://github.com/nkmk/python-snippets/blob/ec0e770a72135b12840ea02f1e74101785faf700/notebook/union_find.py#L1-L46
Merge elements with ʻunion ()→ Get the desired result with
same ()or
group_count ()`.
It doesn't seem difficult
def main():
N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
aa, bb = map(lambda x: int(x) - 1, input().split())
uf.union(aa, bb)
print(uf.group_count() - 1)
def main():
N, M = map(int, input().split())
a, b = [], []
for _ in range(M):
aa, bb = map(int, input().split())
a.append(aa - 1)
b.append(bb - 1)
count = 0
for i in range(M):
uf = UnionFind(N)
for j in range(M):
if j == i:
continue
uf.union(a[j], b[j])
if uf.group_count() != 1:
count += 1
print(count)
def main():
N, M, K = map(int, input().split())
connection = [[] for _ in range(N)]
uf = UnionFind(N)
for i in range(M):
a, b = map(lambda x: int(x) - 1, input().split())
connection[a].append(b)
connection[b].append(a)
uf.union(a, b)
for i in range(K):
c, d = map(lambda x: int(x) - 1, input().split())
if uf.same(c, d):
connection[c].append(d)
connection[d].append(c)
ans = []
for i in range(N):
ans.append(uf.size(i) - len(connection[i]) - 1)
L = [str(i) for i in ans]
print(" ".join(L))
Union Find even for these problems. Whether or not i = p [i] is replaced with ʻuf.same (i, p [i]) `.
def main():
N, M = map(int, input().split())
p = [int(i) - 1 for i in input().split()]
uf = UnionFind(N)
for _ in range(M):
x, y = map(lambda i: int(i) - 1, input().split())
uf.union(x, y)
count = 0
for i in range(N):
if uf.same(i , p[i]):
count += 1
print(count)
Appendix
You can use a lambda expression as the first argument of the map function. Until now, I used to only receive input as a character string and change it to int, but it seems that it can be done collectively by making it a lambda expression when the input value is minus 1 due to the problem of 0-indexed or 1-indexed in the list. ..
map(lambda i: int(i) - 1, input().split())
Recommended Posts