Problem:


Score : 300 points

Problem Statement

There are N cities numbered 1 through N, and M bidirectional roads numbered 1 through M.
Road i connects City A_i and City B_i.

Snuke can perform the following operation zero or more times:

Choose two distinct cities that are not directly connected by a road, and build a new road between the two cities.

After he finishes the operations, it must be possible to travel from any city to any other cities by following roads (possibly multiple times).

What is the minimum number of roads he must build to achieve the goal?

Constraints

2 \leq N \leq 100,000

1 \leq M \leq 100,000

1 \leq A_i < B_i \leq N

No two roads connect the same pair of cities.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

Print the answer.

Sample Input 1

3 1
1 2

Sample Output 1

1

Initially, there are three cities, and there is a road between City 1 and City 2.

Snuke can achieve the goal by building one new road, for example, between City 1 and City 3.
After that,

We can travel between 1 and 2 directly.

We can travel between 1 and 3 directly.

We can travel between 2 and 3 by following both roads (2 - 1 - 3).



Sample input:
3 1
1 2


Sample output:
1

Submission status: Wrong Answer

Solution code:
# https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = map(int, input().split())
uf = UnionFind(N)
ans = 0
for i in range(M):
    A, B = map(int, input().split())
    if not uf.same(A-1,B-1):
        ans += 1
    else:
        uf.union(A-1,B-1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


class UnionFind:
    def __init__(self, n):
        #親要素のノード番号を格納　xが根のとき-(サイズ)を格納
        self.par = [-1 for i in range(n)]
        self.n = n

    def find(self, x):
        #根ならその番号を返す
        if self.par[x] < 0:
            return x
        else:
            #親の親は親
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def is_same(self, x, y):
        #根が同じならTrue
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y: return

        #木のサイズを比較し、小さいほうから大きいほうへつなぐ
        if self.par[x] > self.par[y]:
            x, y = y, x

        self.par[x] += self.par[y]
        self.par[y] = x

    def size(self, x):
        return -self.par[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.par) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __repr__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = NMI()
    uf = UnionFind(N)
    for i in range(M):
        a, b = NMI()
        a, b = a-1, b-1
        uf.unite(a, b)
    print(N - uf.group_count())


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
f=lambda:map(int,input().split())
n,m=f()

# Union Find
p=[-1]*n
def root(x):
  while p[x]>=0: x=p[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return -p[root(x)]

for _ in range(m):
  a,b=f()
  unite(a-1,b-1)
print(n-sum(i<0 for i in p))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
AB=list()
Cities=[False]*N
for i in range(M):
    AB.append(list(map(int,input().split())))
    Cities[AB[i][0]-1]=True
    Cities[AB[i][1]-1]=True
print(Cities.count(False))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
print(max(n-m-1,0))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
data=[0]*n
for i in range(m):
  a,b=map(int,input().split())
  data[a-1]+=1
  data[b-1]+=1
print(data.count(0))

Submission status: Wrong Answer

Solution code:
class Union_Find():
    def __init__(self,N):
        """0,1,...,n-1を要素として初期化する.

        n:要素数
        """
        self.n=N
        self.parents=[-1]*N
        self.rank=[0]*N

    def find(self, x):
        """要素xの属している族を調べる.

        x:要素
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """要素x,yを同一視する.

        x,y:要素
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x]>self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def size(self, x):
        """要素xの属している要素の数.

        x:要素
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """要素x,yは同一視されているか?

        x,y:要素
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """要素xが属している族の要素.
        ※族の要素の個数が欲しいときはsizeを使うこと!!

        x:要素
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """族の名前のリスト
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """族の個数
        """
        return len(self.roots())

    def all_group_members(self):
        """全ての族の出力
        """
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

#=
N,M=map(int,input().split())
U=Union_Find(N)

for _ in range(M):
    A,B=map(int,input().split())
    U.union(A-1,B-1)

print(N-U.group_count())

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
class UnionFindTree:
    def __init__(self, n):
        self._tree = [i for i in range(n)]
        self._rank = [1] * n
    def root(self, a):
        if self._tree[a] == a:return a
        self._tree[a] = self.root(self._tree[a])
        return self._tree[a]
    def is_same_set(self, a, b):
        return self.root(a) == self.root(b)
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._rank[ra] < self._rank[rb]:
            self._tree[ra] = rb
        else:
            self._tree[rb] = ra
            if self._rank[ra] == self._rank[rb]:
                self._rank[ra] += 1

def solve(n, m, x):
    uft = UnionFindTree(n)
    for a,b in x:
        uft.unite(a-1, b-1)
    return n-len(set(uft._tree))

if __name__ == "__main__":
    n,m = map(int, input().split())
    *edges, = [list(map(int, input().split())) for _ in range(m)]
    print(solve(n,m,edges))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
li_input = []

for _ in range(m):
    li_input.append(list(map(int, input().split())))

li_group = []
s_all = set()

for l in sorted(li_input):
    s_all.add(l[0])
    s_all.add(l[1])

    if len(li_group) == 0:
        w_set = set()
        w_set.add(l[0])
        w_set.add(l[1])
        li_group.append(w_set)
    else:
        for g in li_group:
            if l[0] in g or l[1] in g:
                g.add(l[0])
                g.add(l[1])
            else:
                w_set = set()
                w_set.add(l[0])
                w_set.add(l[1])
                li_group.append(w_set)

total = {x for x in range(1, n + 1)}
print(len(li_group) - 1 + len(total.difference(s_all)))

Submission status: Time Limit Exceeded

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
n, m = M()
li = list(itertools.combinations(range(1, n+1), 2))
ans = n-1
for _ in range(m):
    a, b = M()
    if (a, b) in li:
        ans -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def find(x):
    if parent[x]<0:
        return x
    else:
        parent[x]=find(parent[x])
        return parent[x]

def same(x,y):
    return find(x)==find(y)

def union(x,y):
    root_x=find(x)
    root_y=find(y)
    if root_x==root_y:
        return
    if parent[root_x]>parent[root_y]:
        root_x,root_y=root_y,root_x
    parent[root_x]+=parent[root_y]
    parent[root_y]=root_x

def members(n,x):
    root=find(x)
    return [i for i in range(n) if find(i)==root]

def get_size(x):
    return -parent[find(x)]

def get_root():
    return [i for i, root in enumerate(parent) if root<0]

N,M=map(int,input().split())
parent=[-1 for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a=a-1
    b=b-1
    union(a,b)

poe=[]
for i in range(N):
    if i==find(i):
        poe.append((members(N,i)))

ans=len(poe)-1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())

R=list(range(1,N+1))
G=[]
for _ in range(M):
    a,b=map(int,input().split())
    if a in R:
        R.remove(a)
    if b in R:
        R.remove(b)

    flg=True
    n=0
    buf=None
    for i in range(len(G)):
        if a in G[i] and b in G[i]:
            flg=False
            break
        elif a not in G[i] or b not in G[i]:
            pass
        elif a in G[i]:
            n+=1
            flg=False
            if n == 2:
                G[i] = G[i].extend(G.pop(buf))
                break
            else:
                buf=i
                G[i].append(b)
        else:
            n+=1
            flg=False
            if n == 2:
                G[i] = G[i].extend(G.pop(buf))
                break
            else:
                buf=i
                G[i].append(a)
    if flg:
        G.append([a,b])

print(len(G) + len(R) - 1)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())


G=[]
for _ in range(M):
    a,b=map(int,input().split())
    flg=True
    n=0
    buf=None
    for i in range(len(G)):
        if a in G[i] and b in G[i]:
            flg=False
            break
        elif a not in G[i] or b not in G[i]:
            pass
        elif a in G[i]:
            n+=1
            flg=False
            if n == 2:
                G[i] = G[i].union(G.pop(buf))
                break
            else:
                buf=i
                G[i].add(b)
        else:
            n+=1
            flg=False
            if n == 2:
                G[i] = G[i].union(G.pop(buf))
                break
            else:
                buf=i
                G[i].add(a)
    if flg:
        G.append({a,b})


cnt=len(G) - 1
for i in range(1,N+1):
    flg=1
    for g in G:
        if i in g:
            flg=0
            break
    cnt+=flg

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = 'x' in file.mode or 'w' in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b'\n') + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'




def solve():
    n, m = map(int, input().split())

    adj_list = {x: [] for x in range(1, n + 1)}

    for _ in range(m):
        a, b = map(int, input().split())
        adj_list[a].append(b)
        adj_list[b].append(a)

    sets = 0
    visited = {}

    def bfs(curr_node):
        nonlocal visited

        q = [curr_node]

        while q:
            ele = q.pop(0)
            visited[ele] = True
            
            for i in adj_list[ele]:
                if i not in visited:
                    q.append(i)
    
    for i in range(1, n + 1):
        if i not in visited:
            sets += 1
            bfs(i)

    cout<<sets - 1<<endl




def main():
    solve()


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range (M)]
anslist = [i for i in range (N)]
def ketugou(x,y):
  global anslist
  if anslist[x-1] != anslist[y-1]:
    anslist = [anslist[x-1] if anslist[i]==anslist[y-1] else anslist[i] for i in range (N)]
for i in range (M):
  ketugou(AB[i][0],AB[i][1])
anscount = collections.Counter(anslist)
ans = len(anscount) - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
ans = N-1
d = []
for m in range(M):
  A,B = map(int,input().split())
  for i,di in enumerate(d):
    if set([A,B]).issubset(di):
      d[i] = di|set([A,B])
      break
  else:
    d.append(set([A,B]))
    ans -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = map(int,input().split())
uf = UnionFind(n)

for _ in range(m):
    a , b = map(lambda x:int(x)-1,input().split())
    uf.union(a , b)
    
print(len(uf.all_group_members())-1)

Submission status: Time Limit Exceeded

Solution code:
def find(n):
    if root[n] < 0:
        return n
    else:
        root[n] = find(root[n])
        return root[n]

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if root[x] > root[y]:
        x, y = y, x

    root[x] += root[y]
    root[y] = x

def size(x):
    return -root[find(x)]

def same(x,y):
    return find(x) == find(y)

def member(x):
    rt = find(x)
    return [i for i in range(n) if find(i) == rt]

def roots():
    return [i for i, x in enumerate(root) if x < 0]

def member_count(x):
    return len(roots())

def all_group_members():
    return {r: member(r) for r in roots()}

n , m = map(int,input().split())
root = [-1 for i in range(n)]

for _ in range(m):
    a , b = map(lambda x:int(x)-1,input().split())
    unite(a,b)

print(len(all_group_members())-1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())

l = [i for i in range(1,n+1)]

for _ in range(m):
  a,b = map(int,input().split())
  
  for i in range(n):
    if l[i] == l[b-1]:
      l[i] = l[a-1]
      
print(len(list(set(l)))-1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = []
t = [0,0]
index = [0,0]
for i in range(1,n+1):
  a.append([i])
for i in range(m):
  t[0],t[1] = map(int,input().split())
  lf = 0 
  for j in range(len(a)):
    if min(t) in a[j]:
      index[0] = j
      lf += 1
    if max(t) in a[j]:
      index[1] = j
      lf += 1
    if lf > 1:
      break;
  if index[0] != index[1]:
    a[index[0]] += a[index[1]]
    del a[index[1]]
print(len(a)-1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = []
t = [0,0]
index = [0,0]
for i in range(1,n+1):
  a.append([i])
for i in range(m):
  t[0],t[1] = map(int,input().split())
  for j in range(len(a)):
    if min(t) in a[j]:
      index[0] = j
    if max(t) in a[j]:
      index[1] = j
  if index[0] != index[1]:
    a[index[0]] += a[index[1]]
    del a[index[1]]
print(len(a)-1)

Submission status: Time Limit Exceeded

Solution code:
l = input().split()
N = int(l[0])
M = int(l[1])
uf = [i for i in range(N)]
for i in range(M):
  l = input().split()
  la = int(l[0])
  lb = int(l[1])
  minN = min(uf[la-1],uf[lb-1],la-1,lb-1)
  a = uf[la-1]
  b = uf[lb-1]
  uf = [minN if (a==i) or (b==i) else i for i in uf]
  #for j in range(N):
   # if(a==uf[j]) or (b==uf[j]):
    #  uf[j] = minN
  #uf[la-1] = minN
  #uf[lb-1] = minN
retval = 0
for i in range(N):
  if i in uf:
    retval+=1
print(retval-1)

#print(uf)
#s = set(uf)
#print(s)
#print(len(s)-1)

Submission status: Time Limit Exceeded

Solution code:
l = input().split()
N = int(l[0])
M = int(l[1])
uf = [i for i in range(N)]
for i in range(M):
  l = input().split()
  la = int(l[0])
  lb = int(l[1])
  minN = min(uf[la-1],uf[lb-1],la-1,lb-1)
  a = uf[la-1]
  b = uf[lb-1]
  for j in range(N):
    if(a==uf[j]) or (b==uf[j]):
      uf[j] = minN
  #uf[la-1] = minN
  #uf[lb-1] = minN
retval = 0
for i in range(N):
  if i in uf:
    retval+=1
print(retval-1)

#print(uf)
#s = set(uf)
#print(s)
#print(len(s)-1)

Submission status: Time Limit Exceeded

Solution code:
l = input().split()
N = int(l[0])
M = int(l[1])
uf = [i for i in range(N)]
for i in range(M):
  l = input().split()
  la = int(l[0])
  lb = int(l[1])
  minN = min(uf[la-1],uf[lb-1],la-1,lb-1)
  a = uf[la-1]
  b = uf[lb-1]
  for j in range(N):
    if(a==uf[j]) or (b==uf[j]):
      uf[j] = minN
  #uf[la-1] = minN
  #uf[lb-1] = minN


#print(uf)
s = set(uf)
#print(s)
print(len(s)-1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int, input().split())
lst=[list(map(int, input().split()))]
town=[1]*n
for j in range(2):
        town[lst[0][j]-1]=0
l=1
for i in range(m-1):
    a=list(map(int, input().split()))
    for j in range(2):
        town[a[j]-1]=0
    cnt=0
    for k in range(l):
        if (a[0] or a[1]) in lst[k]:
            lst[k].append(a[0])
            lst[k].append(a[1])
            break
        else:
            cnt+=1
        if cnt==l:
            lst.append(a)
            l+=1
                
print(len(lst)+sum(town)-1)
#print(town,lst)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
L = [0] * N
D = {}
c = 1
for i in range(M):
  A, B = map(int, input().split())
  if L[A - 1] == L[B - 1] == 0:
    D[c] = set()
    D[c].add(A)
    D[c].add(B)
    L[A - 1] = c
    L[B - 1] = c
    c += 1
  elif L[A - 1] == 0:
    D[L[B - 1]].add(A)
    L[A - 1] = L[B - 1]
  elif L[B - 1] == 0:
    D[L[A - 1]].add(B)
    L[B - 1] = L[A - 1]
  elif L[A - 1] != L[B - 1]:
    D[L[A - 1]] |= D[L[B - 1]]
    for j in D.pop(L[B - 1]):
      L[j - 1] = L[A - 1]
  #print(L, D, sep = "\n")
print(len(D) + L.count(0) - 1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
if 2*m>(n-1)*(n-2):
  print(0)
else:
  tojo=[-1]*n
  kisyutu=[] 
  g=-1
  me=n
  for i in range(m):
    a,b=map(int,input().split())
    c=tojo[a-1]
    d=tojo[b-1]
    if (c==-1) and (d==-1):
      g=g+1
      tojo[a-1]=i
      tojo[b-1]=i
      kisyutu.append(a-1)
      kisyutu.append(b-1)
      me=me-2
    elif (c==-1) and (d!=-1):
      tojo[a-1]=d
      kisyutu.append(a-1)
      me=me-1
    elif (c!=-1) and (d==-1):
      tojo[b-1]=c
      kisyutu.append(b-1)
      me=me-1
    else:
      if c!=d:
        tojo = [x if x is not d else c for x in tojo]
        g=g-1

  print(g+me)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
if 2*m>(n-1)*(n-2):
  print(0)
else:
  tojo=[-1]*n
  kisyutu=[] 
  g=-1
  me=n
  for i in range(m):
    a,b=map(int,input().split())
    c=tojo[a-1]
    d=tojo[b-1]
    if (c==-1) and (d==-1):
      g=g+1
      tojo[a-1]=i
      tojo[b-1]=i
      kisyutu.append(a-1)
      kisyutu.append(b-1)
      me=me-2
    elif (c==-1) and (d!=-1):
      tojo[a-1]=d
      kisyutu.append(a-1)
      me=me-1
    elif (c!=-1) and (d==-1):
      tojo[b-1]=c
      kisyutu.append(b-1)
      me=me-1
    else:
      if c!=d:
        for j in kisyutu:
          if tojo[j]==d:
            tojo[j]=c
        g=g-1

  print(g+me)

Submission status: Time Limit Exceeded

Solution code:
def search(e_b, g):
    x, y = e_b
    t, s = -1, -1
    for i, e_g in enumerate(g):
        if(x in e_g):
            t = i
        if(y in e_g):
            s = i
        if(t != -1 and s != -1):
            break
    if(t < s):
        t, s = s, t
    return (t, s)

n, m = [int(e) for e in input().split(" ")]
g = [[i + 1] for i in range(n)]
for _ in range(m):
    z = search([int(e) for e in input().split(" ")], g)
    if((z[0] != z[1])):
        g.append([g.pop(z[0]), g.pop(z[1])])
else:
    print(len(g) - 1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
 
tojo=[-1]*n
kisyutu=[] 
g=-1
me=n
for i in range(m):
  a,b=map(int,input().split())
  c=tojo[a-1]
  d=tojo[b-1]
  if (c==-1) and (d==-1):
    g=g+1
    tojo[a-1]=i
    tojo[b-1]=i
    kisyutu.append(a-1)
    kisyutu.append(b-1)
    me=me-2
  elif (c==-1) and (d!=-1):
    tojo[a-1]=d
    kisyutu.append(a-1)
    me=me-1
  elif (c!=-1) and (d==-1):
    tojo[b-1]=c
    kisyutu.append(b-1)
    me=me-1
  else:
    if c!=d:
      for j in kisyutu:
        if tojo[j]==d:
          tojo[j]=c
      g=g-1

print(g+me)

Submission status: Time Limit Exceeded

Solution code:
NM = list(map(int, input().split()))
N = NM[0]
M = NM[1]

xy = [map(int, input().split()) for _ in range(M)]
x, y = [list(i) for i in zip(*xy)]

def my_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

group = []
# for i in range(M):
#     index = -1
#     bo = True
#     for j in range(len(group)):
#         if x[i] in group[j] or y[i] in group[j]:
#             group[j].append(x[i])
#             group[j].append(y[i])
#             # if my_index(group[j], x[i]) != -1:
#             #     index = group.index(x[i])
#             # else:
#             #     index = group.index(y[i])
#             bo = False
#             break
#     if bo:
#         group.append([x[i], y[i]])

for i in range(1, N + 1):
    index = -1
    for j in range(len(group)):
        if i in group[j]:
            index = j
            break
    if index == -1:
        group.append([i])
        index = len(group)-1
    for j in range(M):
        if i == x[j] or i == y[j]:
            group[index].append(x[j])
            group[index].append(y[j])


print(len(group)-1)

Submission status: Time Limit Exceeded

Solution code:
def make_group(n):
    g = []
    for i in range(n):
        g.append([i + 1])
    return g

def search(e_b, g):
    x, y = e_b
    t, s = -1, -1
    for i, e_g in enumerate(g):
        if(x in e_g):
            t = i
        if(y in e_g):
            s = i
    else:
        if(t < s):
            t, s = s, t
    return (t, s)

n, m = [int(e) for e in input().split(" ")]
g = make_group(n)
for _ in range(m):
    z = search([int(e) for e in input().split(" ")], g)
    #print(z)
    if((z[0] == z[1])):
        pass
    else:
        g.append([g.pop(z[0]), g.pop(z[1])])
else:
    print(len(g) - 1)

Submission status: Time Limit Exceeded

Solution code:
NM = list(map(int, input().split()))
N = NM[0]
M = NM[1]

xy = [map(int, input().split()) for _ in range(M)]
x, y = [list(i) for i in zip(*xy)]

def my_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

group = []
# for i in range(M):
#     index = -1
#     bo = True
#     for j in range(len(group)):
#         if x[i] in group[j] or y[i] in group[j]:
#             group[j].append(x[i])
#             group[j].append(y[i])
#             # if my_index(group[j], x[i]) != -1:
#             #     index = group.index(x[i])
#             # else:
#             #     index = group.index(y[i])
#             bo = False
#             break
#     if bo:
#         group.append([x[i], y[i]])

for i in range(1, N + 1):
    index = -1
    for j in range(len(group)):
        if i in group[j]:
            index = j
    if index == -1:
        group.append([i])
        index = len(group)-1
    for j in range(M):
        if i == x[j] or i == y[j]:
            group[index].append(x[j])
            group[index].append(y[j])


print(len(group)-1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
 
tojo=[-1]*n

g=-1
me=n
for i in range(m):
  a,b=map(int,input().split())
  c=tojo[a-1]
  d=tojo[b-1]
  if (c==-1) and (d==-1):
    g=g+1
    tojo[a-1]=i
    tojo[b-1]=i
    me=me-2
  elif (c==-1) and (d!=-1):
    tojo[a-1]=d
    me=me-1
  elif (c!=-1) and (d==-1):
    tojo[b-1]=c
    me=me-1
  else:
    if c!=d:
      for j in range(n):
        if tojo[j]==d:
          tojo[j]=c
      g=g-1
print(g+me)

Submission status: Time Limit Exceeded

Solution code:
def make_group(n):
    g = []
    for i in range(n):
        g.append([i + 1])
    return g

def search(e_b, g):
    x, y = e_b
    t, s = -1, -1
    for i, e_g in enumerate(g):
        if(x in e_g):
            t = i
        if(y in e_g):
            s = i
    else:
        if(t < s):
            t, s = s, t
    return (t, s)

n, m = [int(e) for e in input().split(" ")]
b = []
g = make_group(n)
for _ in range(m):
    b.append([int(e) for e in input().split(" ")])
#print(b)
for e_b in b:
    z = search(e_b, g)
    #print(z)
    if((z[0] == z[1])):
        pass
    else:
        g.append([g.pop(z[0]), g.pop(z[1])])
else:
    print(len(g) - 1)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())

notcalled=list(range(1,N+1))
nets=[]
for _ in range(M):
    a,b=map(int, input().split())
    if a in notcalled and b in notcalled:
        nets.append([a,b])
        del notcalled[notcalled.index(a)]
        del notcalled[notcalled.index(b)]
    elif a in notcalled:
        for net in nets:
            if b in net:
                net.append(a)
        del notcalled[notcalled.index(a)]
    elif b in notcalled:
        for net in nets:
            if a in net:
                net.append(b)
        del notcalled[notcalled.index(b)]
    else:
        for net in nets:
            f=True
            if a in net or b in net:
                if f:
                    q=net.copy
                    del net
                else:
                    net.extend(q)

print(len(nets)-1+len(notcalled))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, m =list(map(int,input().split()))
x=np.array([list(map(int,input().split())) for i in range(m)])

def check_cl(data,num:list):
    if len(num)==0:
        return data
    for i in num:
        tmp = np.unique(x[x[:,0]==i][:,1])
        data = data[data[:,0]!=i]
        data = check_cl(data,tmp)
    else:
        return data

data=x
ans=0
add_times = len(np.arange(1,n+1))-len(np.unique(np.array(x)))

while(1):
    if len(data)==0:
        break
    num=[data[0][0]]
    data =check_cl(data,num)
    ans+=1

print(int(ans-1+add_times))

Submission status: Time Limit Exceeded

Solution code:
import copy
def check_root(root,num):

  if(root[num-1]==num):
    return num
  else:
    ans = check_root(root,root[num-1])
    root[ans-1]=ans
    return ans
  
def reset_root(root):
  new_root = copy.copy(root)
  for i in range(len(root)):
    new_root[i] = check_root(root,i)
  return new_root

def connect_root(root,A,B):
  if root.count(A) < root.count(B):
    root[A-1] = B
  else:
    root[B-1] = A
  #reset_root(root)
  return root

def count_root(root):
  root_num = []
  for i in range(len(root)):
    flag = 0
    for j in range(len(root_num)):
      if ( root[i]==root_num[j]):
        flag=1
    if(flag==0):
      root_num.append(root[i])
  return len(root_num)
  

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

load = [list(map(int,input().split())) for _ in range(M)]

root =[]
for i in range(N):
  root.append(i+1)
  

for i in range(M):
  root_A =check_root(root,load[i][0])
  root_B =check_root(root,load[i][1])
  if not (root_A==root_B):
    connect_root(root,root_A,root_B)
  if (i%50==0):
    reset_root(root)

root = reset_root(root)
print(count_root(root)-1)