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: Time Limit Exceeded

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

  if(root[num-1]==num):
    return num
  else:
    return check_root(root,root[num-1])
  
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] = B
  else:
    root[B] = 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)


print(count_root(root)-1)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np

from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

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

cities = [[0] * N for i in range(N)]
# print(cities)

cities = np.array(cities)

for i in range(M):
    i1, i2 = map(int, input().split())
    cities[i1-1][i2-1] = 1
    cities[i2-1][i1-1] = 1
#     print(cities)
    
# print(cities)

n, labels = connected_components(csr_matrix(cities))
print(n-1)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
C=[0]*N
count=0
true_count=0
for i in range(M):
  A,B=map(int,input().split())
  if C[A-1]==0 and C[B-1]==0:
    count+=1
    true_count+=1
    C[B-1]=count
    C[A-1]=count
  elif C[A-1]==0:
    C[A-1]=C[B-1]
  elif C[B-1]==0:
    C[B-1]==C[A-1]
  else:
    C[B-1]=min(C[A-1],C[B-1])
    C[A-1]=min(C[A-1],C[B-1])
    true_count-=1
    for i in range(N):
      if C[i]==max(C[A-1],C[B-1]):
        C[i]=min(C[A-1],C[B-1])
for i in range(N):
  if C[i]==0:
    true_count+=1
print(true_count-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    connect_list = [0] * N

    max_road_num = 0
    for i in range(M):
        A, B = map(int, input().split())
        A = A - 1
        B = B - 1
        
        A_road_num = connect_list[A]
        B_road_num = connect_list[B]

        if A_road_num == 0 and B_road_num == 0:
            max_road_num = max_road_num + 1
            connect_list[A] = max_road_num
            connect_list[B] = max_road_num
        elif A_road_num != 0 and B_road_num == 0:
            connect_list[B] = connect_list[A]
        elif A_road_num == 0 and B_road_num != 0:
            connect_list[A] = connect_list[B]
        else:
            connect_list = [A_road_num if B_road_num == road_num else road_num for road_num in connect_list]

    answer = 0
    set_connect_list = set(connect_list)
    set_connect_list.discard(0)
    if len(set_connect_list) != 1:
        answer = len(set_connect_list) - 1

    print(answer + connect_list.count(0))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
class UnionFind():
	"""docstring for UnionFind"""
	def __init__(self, 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
        
n,m=input2()
AB=[input_array() for _ in range(m)]
D=[[0]*n for _ in range(n)]

uf = UnionFind(n)
for ab in AB:
	a=ab[0]
	b=ab[1]
	uf.union(a-1,b-1)

ans=0
for i in range(n):
	tmp=uf.find(i)
	if tmp!=0:
		ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(x) for x in input().split()]

f = [[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
    i, j = [int(x) for x in input().split()]
    f[j - 1][i - 1] = 1

ans = 0
for x in range(1, N):
    if sum(f[x][:x]) == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
arr = []
for i in range(m):
    a, b = map(int, input().split())
    if [a,b] not in arr:
        arr.append([a,b])

print(n-1-len(arr))

Submission status: Time Limit Exceeded

Solution code:
import collections

n, m = map( int, input().split() )
#print( n, m )


x = list( range( n ) )
#print( x )

for i in range( m ):
    ai, bi =  map( int, input().split() )
    if x[ ai-1 ] != x[ bi-1 ]:
        for i in range( n ):
            if x[ i ] == x[ bi-1 ]:
                x[ i ] = x[ ai-1 ]

#print( x )

c = collections.Counter( x )
#print( c )
print( len( c ) - 1 )

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
tree = [[None,None] for i in range(N+1)]
for _i in range(M):
  small,big = map(int,input().split())
  while tree[big][0] is not None:
    big = tree[big][0]
  while tree[small][1] is not None:
    small = tree[small][1]
  tree[big][0] = small
  tree[small][1] = big
print(len([i for i in tree if i[0] is None])-2)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
def dfs(A,N,M,i,j,visited):
    visited[i][j]=1
    rn=[-1,-1,-1,0,0,1,1,1]
    cn=[-1,0,1,-1,1,-1,0,1]
    for s in range(8):
        r=i+rn[s]
        c=j+cn[s]
        if r>=0 and r<N and c>=0 and c<M and not visited[r][c] and A[r][c]:
            dfs(A,N,M,r,c,visited)

from collections import defaultdict
n,m=map(int,input().split())
A=[[0 for i in range(n)] for i in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    A[a-1][b-1]=1
    A[b-1][a-1]=1
count=0
visited=[[0 for i in range(n)] for i in range(n)]
for i in range(n):
    for j in range(n):
        if A[i][j] and not visited[i][j]:
            count+=1
            dfs(A,n,n,i,j,visited)
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools

city, road = map(int, input().split())

pairs = []
for i in range(road):
  pair = list(map(int, input().split()))
  pairs.append(pair)
  
li = list(itertools.chain.from_iterable(pairs))
no = 0
for i in range(city):
  if i not in li:
    no += 1

li_solo = []

def collect(pairs, no):
  for i in range(len(pairs)):
    if len(pairs) < 1:
      break
    pair = pairs.pop(-1)
    pair_check = 0
    for j in range(len(pairs)):
      if len(set(pair) & set(pairs[j])) > 0:
        pairs[j].extend(pair)
        break
    else:
      no += 1
  return pairs, no

while(len(pairs) > 0):
  pairs, no = collect(pairs, no)
  
print(no - 1)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

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

cities = [[0] * N for i in range(N)]
# print(cities)

for i in range(M):
    i1, i2 = map(int, input().split())
    cities[i1-1][i2-1] = 1
    cities[i2-1][i1-1] = 1
#     print(cities)
    
# print(cities)

n, labels = connected_components(csr_matrix(cities))
print(n-1)

Submission status: Time Limit Exceeded

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

kosuu = 0

for i in  range(M):
    A,B = map(int,input().split())
    A,B = min(A,B),max(A,B)
    tem.append([A,B])

tem = sorted(tem)
tem1 = [tem[0]]

for i in range(M):
    A,B = tem[i][0],tem[i][1]
    
    for j in range(len(tem1)):
        l = tem1[j]
        
        if A in l or B in l:
            tem1[j] = list(set(l+[A,B]))
        else:
            tem1.append([A,B])

for k in range(len(tem1)):
    kosuu += len(tem1[k])
    
print(N - kosuu + len(tem) - 1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=list()
b=list()
ans=int(0)
city=[0]*(n+1)
for i in range(m):
	a,b=map(int,input().split())
	if (city[a] == 0) and (city[b] == 0):
		ans=ans+1
		city[a]=ans
		city[b]=ans

	elif (city[a] != 0) and (city[b] == 0):
		city[b]=city[a]

	elif (city[a] == 0) and (city[b] != 0):
		city[a]=city[b]

	elif (city[a] <= city[b]):
		x=city[b]
		y=city[a]
		for j in range(n+1):
			if city[j] == x:
				city[j]=y

	else:
		y=city[b]
		x=city[a]
		for j in range(n+1):
			if city[j] == x:
				city[j]=y
i=int(1)
p=int(0)
while i <= ans:
	if i in city:
		p=p+1
	i=i+1


print(p+city.count(0)-2)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

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

L = [[0] * N] * N
for _ in range(M):
    a,b = map(int, input().split())
    L[a-1][b-1] = 1

csr = csr_matrix(L)
n = connected_components(csr, return_labels=False)
print(n)

Submission status: Time Limit Exceeded

Solution code:
import collections
n,m=map(int,input().split())
road=[[] for i in range(n)]
for i in range(m):
    a,b= map(int,input().split())
    road[a-1].append(b-1)
    road[b-1].append(a-1)

d=[-1]*n
d[0]=0
q=collections.deque()
q.append(0)
count= 1
flag=True
while flag:
    while len(q)>0:
        cur=q.popleft()
        for dst in road[cur]:
            if d[dst]==-1:
                d[dst]=d[cur]
                q.append(dst)
    flag=False
    for i in range(n):
        if d[i]==-1:
            count+=1
            flag=True
            q.append(i)
            d[i]=count
            break
            
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
xy = [map(int, input().split()) for _ in range(m)]
x, y = [list(i) for i in zip(*xy)]
arr = [1]*n
for i in range(len(x)):
    arr[x[i]-1] = 0
    if x[i] == y[i]:
        pass
    else:
        ans_y = [k for k,p in enumerate(y) if p == y[i]]
        ans_x = [k for k, p in enumerate(x) if p == y[i]]
        for j in range(len(ans_y)):
            arr[y[ans_y[j]]-1] = 0
            y[ans_y[j]] = x[i]
        for j in range(len(ans_x)):
            x[ans_x[j]] = x[i]
print(len(list(set(x)))-1+sum(arr))

Submission status: Time Limit Exceeded

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

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

connect = {0: set(AB[0])}
no_connection = [n + 1 for n in range(N)]

group_idx = 0

for a, b in AB: 
  
  if a in no_connection:
    no_connection.remove(a)
  
  if b in no_connection:
    no_connection.remove(b)
  
  if b in connect[group_idx]:
    connect[group_idx] |= set([a, b])
      
  else:
    group_idx += 1
    connect[group_idx] = set([a, b])
      
print(len(connect) - 1 + len(no_connection))

Submission status: Time Limit Exceeded

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

A=[[0 for i in range(n)] for j in range(n)]
B=[0 for i in range(n)]

for i in range(m):
  a,b=map(int,input().split(" "))
  if a<=b:
    A[a-1][b-1]=1
  else:
    A[b-1][a-1]=1
  B[a-1]=1
  B[b-1]=1
    
g=0
G=[[0]]
for i in range(n):
  for j in range(i+1,n):
    if A[i][j]==1:
      for k in G:
        if i in k:
          k.append(j)
        else:
          G.append([i,j])
          
ans=len(G)+(n-sum(B))-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

group = []
for _ in range(M):
    A, B = map(int, input().split())
    if len(group) == 0:
        group.append([A, B])
    else:
        A_idx = -1
        B_idx = -1
        for i in range(len(group)):
            if A in group[i]:
                A_idx = i
                break
        for i in range(len(group)):
            if B in group[i]:
                B_idx = i
                break
        if A_idx == B_idx == -1:
            group.append([A, B])
        elif A_idx == B_idx:
            pass
        elif A_idx == -1:
            group[B_idx] = group[B_idx] + [A]
        elif B_idx == -1:
            group[A_idx] = group[A_idx] + [B]
        else:
            group[A_idx] = group[A_idx] + group[B_idx]
            group.remove(group[B_idx])

group_elements = []
for i in range(len(group)):
    group_elements += group[i]

ans = 0
for i in range(N):
    if (i + 1) in group_elements:
        pass
    else:
        ans += 1

ans += len(group) - 1
print(ans)

Submission status: Time Limit Exceeded

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

roads = []
checkpoints = [0] * n
countMakeRoads = -1

for i in range(m):
    aiBi = list(map(int, input().strip().split()))
    roads.append(aiBi)

for i in range(n):
    if checkpoints[i] == i+1:
        continue
    else:
        canContinue = False
        for j in range(m):
            if roads[j][0] == i+1:
                if roads[j][1] == checkpoints[roads[j][1]-1]:
                    canContinue = True
                    break;
        if canContinue == True:
            continue;
        countMakeRoads += 1
        checkpoints[i] = i+1
        for k in range(m):
            if roads[k][0] == i+1:
                checkpoints[roads[k][1] - 1] = roads[k][1]
print(countMakeRoads)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

N = 10**5+1
g = [[] for i in range(N)]

vis = [False for i in range(N)]

good = [False for i in range(N)] 
  
def ADD_EDGE(u, v): 
    g[u].append(v)
    
def dfs1(v): 
    good[v] = True
    for to in g[v]: 
        if not good[to]: 
            dfs1(to)
            
def dfs2(v):
    global cnt 
    vis[v] = True
    cnt += 1
    for to in g[v]: 
        if not vis[to] and not good[to]: 
            dfs2(to)
            
def Minimum_Edges():
    global vis, cnt
    dfs1(x)
    
    val = [] 
  
    for i in range(0, n):
        if not good[i]: 
            cnt = 0
            vis = [False for i in range(N)]
            
            dfs2(i) 
            val.append((cnt, i))
            
    val.sort(reverse = True)
    
    ans = 0
    for it in val:  
        if not good[it[1]]:  
            ans += 1
            dfs1(it[1]) 
  
    return ans



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

for _ in range(m):
    a, b = map(int, input().split())
    ADD_EDGE(a, b)
    ADD_EDGE(b, a)

x = m

print(Minimum_Edges())

##N, Q = map(int, input().split())
##s = '1'*N
##for _ in range(Q):
##    l, r, d = map(int, input().split())
##    s = s[:l-1] + str(d)*(r-l+1) + s[r:]
##    print(int(s) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    connect_list = [0] * N

    max_road_num = 0
    for i in range(M):
        A, B = map(int, input().split())
        A = A - 1
        B = B - 1
        
        A_road_num = connect_list[A]
        B_road_num = connect_list[B]

        if A_road_num == 0 and B_road_num == 0:
            max_road_num = max_road_num + 1
            connect_list[A] = max_road_num
            connect_list[B] = max_road_num
        elif A_road_num != 0 and B_road_num == 0:
            connect_list[B] = connect_list[A]
        elif A_road_num == 0 and B_road_num != 0:
            connect_list[A] = connect_list[B]
        else:
            connect_list = [A_road_num if B_road_num == road_num else road_num for road_num in connect_list]

    answer = 0
    set_connect_list = set([i for i in connect_list if i > 0])
    if len(set_connect_list) != 1:
        answer = len(set_connect_list) - 1

    print(answer + connect_list.count(0))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
li = [list(map(int, input().split())) for i in range(m)]

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())

class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))

        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}

    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]

    def union(self, x, y):
        super().union(self.d[x], self.d[y])

    def size(self, x):
        return super().size(self.d[x])

    def same(self, x, y):
        return super().same(self.d[x], self.d[y])

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

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

l=[]
for i in range(n):
  l.append(i+1)

ufl = UnionFindLabel(l)
for a in li:
  ufl.union(a[0], a[1])
sum=len(ufl.all_group_members().values())-1
print(sum)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

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

L = [[0] * N] * N
for _ in range(M):
    a,b = map(int, input().split())
    L[a-1][b-1] = 1

n,l = connected_components(csr_matrix(L))
print(n)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(x) for x in input().split()]

f = [[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
    i, j = [int(x) for x in input().split()]
    f[j - 1][i - 1] = 1

ans = 0
for x in range(1, N):
    if sum(f[x]) == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M= [int(x) for x in input().split()]

root = list(range(N))

for i in range(M):
    A,B = [int(x)-1 for x in input().split()]
    a = root[A]
    b = root[B]
    if a<b:
        root = [a if i == b else i for i in root]
    if b<a:
        root = [b if i == a else i for i in root]

print(len(set(root))-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools

city, road = map(int, input().split())

pairs = []
for i in range(road):
  pair = list(map(int, input().split()))
  pairs.append(pair)
  
li = list(itertools.chain.from_iterable(pairs))
no = 0
for i in range(city):
  if i not in li:
    no += 1

li_solo = []

def collect(pairs):
  for i in range(len(pairs)):
    if len(pairs) < 1:
      break
    pair = pairs.pop(-1)
    pair_check = 0
    for j in range(len(pair)):
      num = pair[j]
      for k in range(len(pairs)):
        if num in pairs[k]:
          pairs[k].extend(pair)
          pair_check = 1
          break
      if pair_check == 1:
        break
    if pair_check == 0:
      li_solo.append(pair)
  return pairs

while(len(pairs) > 0):
  pairs = collect(pairs)
  
print(len(li_solo) + no -1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
roads = set()
dic = {x:set() for x in range(1, n + 1)}

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

  for i in dic[1]:
      dic[1] = set(list(dic[1]) + list(dic[i]))

count = 0
for i in range(1, n + 1):
    if i not in dic[1]:
        count += 1
        dic[1] = set(list(dic[1]) + [i] + list(dic[i]))

print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections
n, m = map(int, input().split())
linked = collections.defaultdict(set)
for i in range(1, n + 1):
  linked[i].add(i)

for i in range(m):
  a, b = map(int, input().split())
  if linked[a] == linked[b]:continue
  if len(linked[a]) > len(linked[b]):
     tmp = a
     a = b
     b = tmp
  linked[a].update(linked[b])
  tmp =linked[a]

  for t in linked[b]:
    linked[t] = tmp

n_connected = 0
n_group = 0
for s in linked.values():
  if s:
    n_group += 1
    n_connected += len(s)
    s.clear()
print((n - n_connected) + (n_group - 1))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
tem = []
kosuu = 0

for i in  range(M):
    A,B = map(int,input().split())
    
    if len(tem) == 0:
        tem.append([A,B])
        kosuu += 2
    else:
        for i in range(len(tem)):
            l = tem[i]
            if A in l or B in l:
                tem[i] = (list(set(l + [A,B])))
                kosuu += 1
                break
            else:
                tem.append([A,B])
                kosuu += 2

print(N - kosuu + len(tem) - 1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from heapq import heappop, heappush
    

def resolve(T,v):
    while v != T[v]:
        v = T[v]
    return v

def solve():
    N, M = map(int, input().split())
    E = set()
    for _ in range(M):
        a, b = map(int, input().split())
        E.add((a-1,b-1))

    T = list(range(N))
    while E:
        e = E.pop()
        u, v = e
        lu = resolve(T,u)
        lv = resolve(T,v)
        if lv == lu:
            continue
        T[lu] = lv
        continue

    return len(set(resolve(T,v) for v in range(N)))-1

if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
li = [list(map(int, input().split())) for i in range(m)]

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())

class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))

        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}

    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]

    def union(self, x, y):
        super().union(self.d[x], self.d[y])

    def size(self, x):
        return super().size(self.d[x])

    def same(self, x, y):
        return super().same(self.d[x], self.d[y])

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

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

l=[]
for i in range(n):
  l.append(i+1)

ufl = UnionFindLabel(l)
for a in li:
  ufl.union(a[0], a[1])
sum=-1
for v in ufl.all_group_members().values():
  sum = sum + 1
print(sum)

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int,input().split()))

N = a[0]
M = a[1]

cities = [0] * N
lands = [[]] * N

roads = []
for i in range(M):
    a = list(map(int,input().split()))
    roads.append([a[0], a[1]])

for r in roads:
    if cities[r[0]-1] == 0:
        cities[r[0]-1] = r[0]
        #lands[r[0] - 1] = [r[0]]
    #else:
    #    for i in range(N):
    #        if cities[i] == cities[r[0]-1]:
    #            cities[i] = r[0]

    if cities[r[1]-1] == 0:
        cities[r[1]-1] = r[0]
    else:
        for i in range(N):
            if cities[i] == cities[r[1]-1]:
                cities[i] = r[0]

#print(cities)
found = {}
zero_count = 0
for i in range(N):
    if cities[i] != 0:
        found[cities[i]] = 1
    else:
        zero_count += 1

print(len(found) - 1 + zero_count)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
n,m = map(int, input().split())
ab = []
c = [set() for i in range(n)]

for i in range(m):
  a = list(map(int, input().split()))
  a.sort()
  x,y = a[0]-1,a[1]-1
  c[x].add(y)
  c[y].add(x)

def dfs(s):
  if vis[s] == False:
    ary.append(s)
    vis[s] = True
    for j in c[s]:
      dfs(j)



vis = [False for i in range(n)]

ans= []

for i in range(n):
  ary = []
  dfs(i)
  if len(ary) == 0:
    continue
  ans.append(len(ary))

print (len(ans)-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

group = [[i] for i in range(N + 1)]
group.remove([0])
for _ in range(M):
    A, B = map(int, input().split())
    if len(group) == 0:
        group.append([A, B])
    else:
        A_idx = -1
        B_idx = -1
        for i in range(len(group)):
            if A in group[i]:
                A_idx = i
                break
        for i in range(len(group)):
            if B in group[i]:
                B_idx = i
                break
        if A_idx == B_idx == -1:
            group.append([A, B])
        elif A_idx == B_idx:
            pass
        elif A_idx == -1:
            group[B_idx] = group[B_idx] + [A]
        elif B_idx == -1:
            group[A_idx] = group[A_idx] + [B]
        else:
            group[A_idx] = group[A_idx] + group[B_idx]
            group.remove(group[B_idx])

ans = len(group) - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*
import sys

N, M = map(int,input().split())
AB = [0]*N
c = 1
for i in range(M):
  nyu = list(map(int,input().split()))
  if AB[nyu[0]-1] == 0 and AB[nyu[1]-1] == 0:
    AB[nyu[0]-1] = c
    AB[nyu[1]-1] = c
    c += 1
  elif AB[nyu[0]-1] != 0:
    if AB[nyu[1]-1] == 0:
      AB[nyu[1]-1] = AB[nyu[0]-1]
    else:
      tmp = AB[nyu[1]-1]
      for i in range(N):
        if AB[i] == tmp:
          AB[i] = AB[nyu[0]-1]
  elif AB[nyu[1]-1] != 0:
    if AB[nyu[0]-1] == 0:
      AB[nyu[0]-1] = AB[nyu[1]-1]
    else:
      tmp = AB[nyu[0]-1]
      for i in range(N):
        if AB[i] == tmp:
          AB[i] = AB[nyu[1]-1]

zero = 0
for i in range(N):
  if AB[i] == 0:
    zero += 1
print(max(AB) + zero -1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
path_one_list = []
path_two_list = []
count = 0
for i in range(m):
    a,b = map(int,input().split())
    if (a in path_one_list and b in path_two_list) or (b in path_one_list and a in path_two_list):
        path_one_list.append(a)
        path_two_list.append(b)
    else:
        path_one_list.append(a)
        path_two_list.append(b)
        count +=1
print(n-1-count)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=list()
b=list()
for i in range(m):
	c,d=map(int,input().split())
	a.append(c)
	b.append(d)
ans=int(0)
city=[0]*(n+1)
for i in range(m):
	if (city[a[i]] == 0) and (city[b[i]] == 0):
		ans=ans+1
		city[a[i]]=ans
		city[b[i]]=ans

	elif (city[a[i]] != 0) and (city[b[i]] == 0):
		city[b[i]]=city[a[i]]

	elif (city[a[i]] == 0) and (city[b[i]] != 0):
		city[a[i]]=city[b[i]]

	elif (city[a[i]] <= city[b[i]]):
		x=city[b[i]]
		y=city[a[i]]
		for j in range(n+1):
			if city[j] == x:
				city[j]=y

	else:
		y=city[b[i]]
		x=city[a[i]]
		for j in range(n+1):
			if city[j] == x:
				city[j]=y
i=int(1)
p=int(0)
while i <= ans:
	if i in city:
		p=p+1
	i=i+1


print(p+city.count(0)-2)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
cities = [0]*N
for i in range(M):
    a, b = map(int, input().split())
    if cities[a-1] and cities[b-1]:
        temp_a = cities[a-1]
        temp_b = cities[b-1]
        for j in range(N):
            if cities[j]==temp_b:
                cities[j]=temp_a
    elif cities[a-1]:
        cities[b-1] = cities[a-1]
    elif cities[b-1]:
        cities[a-1] = cities[b-1]
    else:
        count=max(cities)
        cities[a-1] = count+1
        cities[b-1] = count+1
if 0 in cities:
    print(cities.count(0)+len(set(cities))-2)
else:
    print(len(set(cities)) - 1)

Submission status: Time Limit Exceeded

Solution code:
n,m = list(map(int,input().split()))
c = []
cn = []
for _ in range(m):
  i,j = list(map(int,input().split()))
  if (not i in c) and (not j in c):
    c+=[i,j]
    cn.append([i,j])
  elif (not i in c):
    c.append(i)
    for a,x in enumerate(cn):
      if j in x:
        cn[a].append(i)
  elif (not j in c):
    c.append(j)
    for a,x in enumerate(cn):
      if i in x:
        cn[a].append(j)
  else:
    p = None
    idx = None
    for a,x in enumerate(cn):
      if i in x:
        if j in x:
          break
      if p == None:
        idx = a
        p = x
      else:
        cn.pop(a)
        cn.pop(idx)
        cn.append(x+p)
        break
print(n-1-len(c)+len(cn))

Submission status: Time Limit Exceeded

Solution code:
import collections
n, m = map(int, input().split())
linked = collections.defaultdict(set)
for i in range(1, n + 1):
  linked[i].add(i)

for i in range(m):
  a, b = map(int, input().split())
  if len(linked[a]) > len(linked[b]):
     tmp = a
     a = b
     b = tmp
  linked[a].update(linked[b])
  tmp =linked[a]

  for t in linked[b]:
    linked[t] = tmp

n_connected = 0
n_group = 0
for s in linked.values():
  if s:
    n_group += 1
    n_connected += len(s)
    s.clear()
print((n - n_connected) + (n_group - 1))