Submission #1698624

---

Source Code Expand

from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))

n,m = readLine_int_list()
v = [i for i in range(n)]
    
def get_root(n):
    if n == v[n]:
        return n
    else:
        v[n] = get_root(v[n])
        return v[n]

def unite(a,b):
    a, b = get_root(a), get_root(b)
    if a!=b:
        v[b] = a
def same(a,b):
    return get_root(a) == get_root(b)

def main():
    for i in range(m):
        a,b =readLine_int_list()
        unite(a-1,b-1)
    
    print(len({get_root(n) for n in set(v)})-1)
    
if __name__ == '__main__':
    main()

Submission Info

Judge Result