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 networkx as nx
# import matplotlib.pyplot as plt
N,M = list(map(int,input().split()))
AB=[list(map(int, input().split())) for i in range(M)]

if len(AB)==1:
    print(N-2)
else:
    G=nx.Graph()
    G.add_nodes_from(range(1,N+1))
    G.add_edges_from(AB)

    count=0

    nodes=set(range(1,N+1))
    p_ori=list(nodes)[0]
    reachable=nx.shortest_path(G,p_ori).keys()
    nodes-=set(reachable)
    while nodes!=set():
        p=list(nodes)[0]
        reachable=nx.shortest_path(G,p).keys()
        nodes-=set(reachable)
        G.add_edge(p,p_ori)
        count+=1
        
    print(count)
    # nx.draw_networkx(G)

    # plt.show()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
l = []
cnt = 0
for i in range (m):
    a, b = map(int, input().split()) 
    if (a in l) or (b in l):
        l.append(a)
        l.append(b)
        
    else:
        l.append(a)
        l.append(b)
        cnt += 1
        
    l =list(set(l))

l = set(l)
x = n - len(l) 

print(cnt+x-1)

Submission status: Time Limit Exceeded

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

rootedPoints = set()
points = []

for _ in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  rootedPoints.add(A)
  rootedPoints.add(B)
  Aindex = False
  Bindex = False
  for i, ps in enumerate(points):
    if A in ps: Aindex = i
    if B in ps: Bindex = i
    if Aindex is not False and Bindex is not False: break
  if Aindex is False and Bindex is False:
    points.append({A, B})
  elif Aindex is False:
    points[Bindex].add(A)
  elif Bindex is False:
    points[Aindex].add(B)
  elif Aindex!=Bindex:
    points[Aindex] |= points[Bindex]
    points[Bindex] = {}
  #print(points)
print(len(tuple(pp for pp in points if len(pp)!=0))-1+N-len(rootedPoints))

Submission status: Time Limit Exceeded

Solution code:
import collections

[_num_of_cities, _num_of_roads] = list(map(int, input().split(" ")))
_cities = [0 for _i in range(_num_of_cities)]
for _i in range(_num_of_roads):
  [_a, _b] = list(map(int, input().split(" ")))
  if _b == _num_of_cities:
    _b = 0
  if _cities[_a] == 0:
    if _cities[_b] == 0:
      _cities[_a] = _cities[_b] = _i + 1
    else:
      _cities[_a] = _cities[_b]
  else:
    if _cities[_b] == 0:
      _cities[_b] = _cities[_a]
    else:
      _x = _cities[_b]
      _cities[_b] = _cities[_a]
      for _j in range(_num_of_cities):
        if _cities[_j] == _x:
          _cities[_j] = _cities[_a]

_group = len(collections.Counter(_cities))
_alone = _cities.count(0)
if _alone == 0:
  print(_group - 1)
else:
  print(_group - 2 + _alone)

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = list(map(int, sys.stdin.readline().strip().split(" ")))

clusters = [set([a]) for a in range(1, N + 1)]
for m in range(M):
    s, t = list(map(int, sys.stdin.readline().strip().split(" ")))

    merge_ids = []
    count = 0
    for i, c in enumerate(clusters):
        if s in c:
            merge_ids.append((i, s))
            count += 1
        if t in c:
            merge_ids.append((i, t))
            count += 1
        if count == 2:
            break

    if len(merge_ids) == 2:
        sc, tc = merge_ids
        if sc[0] != tc[0]:
            clusters[sc[0]] |= clusters[tc[0]]
            del clusters[tc[0]]

print(len(clusters) - 1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
list = []
for i in range(1,n+1):
  list.append(i)
for i in range(m):
  a, b = map(int,input().split())
  c = max(list[a-1],list[b-1])
  list = [min(list[a-1],list[b-1]) if i == c else i for i in list]
ans = len(set(list))-1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# TLEで無理ィィ
numbers = list(map(int, input().split()))
# N...街の数
# M...道路の数
N = numbers[0]
M = numbers[1]
c1 = [0] * M
c2 = [0] * M
groups = []

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

for i in range(M):
    c1[i], c2[i] = map(int, input().split())

for i in range(M):
    f = 0
    s = 0
    for j in range(len(groups)):
        if c1[i] in groups[j]:
            f = j
        if c2[i] in groups[j]:
            s = j
    a = groups[f]
    for i in a:
        groups[s].append(i)
    del groups[f]

print(len(groups) - 1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
roads = [list(map(int, input().split())) for i in range(M)]

useless = 0
linked = []
for road in roads:
    is_0 = False
    is_1 = False
    if road[0] in linked:
        is_0 = True
    else:
        linked.append(road[0])

    if road[1] in linked:
        is_1 = True
    else:
        linked.append(road[1])

    if is_0 and is_1:
        useless += 1

result = N - 1 - M + useless
print(result)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
    # ノードxのrootノードを見つける
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
    # 木の併合、入力は併合したい各ノード⇒(a,b)
        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):
    # ノードxが属する木のサイズを返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
    # 入力ノード(x,y)が同じグループに属するかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
    #ノード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())

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n,m=map(int,input().split())
u=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    u.unite(a,b)
ans=0
for i in range(n):
    ans=u.roots()
print(len(ans)-1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
l = []
cnt = 0
for i in range (m):
    a, b = map(int, input().split()) 
    if (a in l) or (b in l):
        l.append(a)
        l.append(b)
        
    else:
        l.append(a)
        l.append(b)
        cnt += 1

l = set(l)
x = n - len(l) 

print(cnt+x-1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
l = []
c = 1
for i in range(M):
  a, b = map(int, input().split())  
  if a not in l and b not in l:
    c += 1
  l += [a, b]
print(N - c)

Submission status: Time Limit Exceeded

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

ab = [set(map(int, input().split())) for _ in range(m)]

n_set = {n for n in range(1,n+1)}

bubun = []
bubun.append(ab[0])
n_set -= ab[0]

for i in range(1,m-1):
    n_set -= ab[i]
    for j in range(len(bubun)):
        if not ab[i].isdisjoint(bubun[j]):
            bubun[j] |= ab[i]
        else:
            bubun.append(ab[i])

size_old = len(bubun)
while True:
    for i in range(len(bubun)):
        for j in range(i+1, len(bubun)):
            if not bubun[i].isdisjoint(bubun[j]):
                bubun[i] |= bubun[j]
                del bubun[j]
            if len(bubun) != size_old:
                size_old = len(bubun)
                break

    if len(bubun) != size_old:
        size_old = len(bubun)
        countinue
    else:
        break

print(len(n_set) + len(bubun) - 1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
 
dp = [[0] * N for j in range(N)]
 
for i in range(M):
    a, b = map(int, input().split())
    dp[a-1][b-1] = 1
    dp[b-1][a-1] = 1
print(dp.count([0]*N))

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)

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

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
C=[0]*N
team=0
count=N-1
for i in range(M):
  A,B=map(int,input().split())
  if C[A-1]==0 and C[B-1]==0:
    team+=1
    count-=1
    C[B-1]=team
    C[A-1]=team
  elif C[A-1]==0:
    C[A-1]=C[B-1]
    count-=1
  elif C[B-1]==0:
    C[B-1]==C[A-1]
    count-=1
  elif C[B-1]==C[A-1]:
    count=count
  else:
    C[B-1]=min(C[A-1],C[B-1])
    C[A-1]=min(C[A-1],C[B-1])
    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])
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
l = []
c = 1
for i in range(M):
  a, b = map(int, input().split())  
  if a not in set(l) and b not in set(l):
    c += 1
  l += [a, b]
print(N - c)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
 
road = [[0 for j in range(N)] for i in range(N)]
count = 0
 
for n in AB:
    road[n[0]-1][n[1]-1] = 1
    road[n[1]-1][n[0]-1] = 1

for n in road:
    if sum(n) == 0:
        count += 1
 
print(count)

Submission status: Time Limit Exceeded

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

num = []

for i in range(M):
    a, b = map(int, input().split())
    if not(a in num):
        num.append(a)
    if not(b in num):
        num.append(b)

if M < N:
    print(N - M - 1)
else:
    print(N - len(num))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = [int(x) for x in input().split()]
  
def dfs(i, flag, A, B):
  Next = list()
  deli = list()
  a = list(); b = list()
  for j in range(len(A)):
    if(A[j]==(1+i)):
      Next.append(B[j])
      deli.append(j)
    if(B[j]==(1+i)):
      Next.append(A[j])
      deli.append(j)
    else:
      a.append(A[j])
      b.append(B[j])
  A = a
  B = b
  if(len(Next)!=0):
    for j in range(len(Next)):
      if(flag[Next[j]-1]==0):
        flag[Next[j]-1] = 1
        flag = dfs(Next[j]-1, flag, A, B)
  return flag

if __name__=='__main__':
  A = list()
  B = list()
  for i in range(M):
    a, b = [int(x) for x in input().split()]
    A.append(a)
    B.append(b)
  ans = 0
  flag = [0 for _ in range(N)]
  i = 0
  flag[i] = 1
  mada = [i for i in range(N) if(flag[i]==0)]
  while True:    
    flag = dfs(i, flag, A, B)
    mada = [i for i in range(N) if(flag[i]==0)]
    if(len(mada) == 0):
      break
    i = mada[0]
    flag[i] = 1
    ans += 1
  print(ans)

Submission status: Time Limit Exceeded

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

ab = [set(map(int, input().split())) for _ in range(m)]

n_set = {n for n in range(1,n+1)}

bubun = []
bubun.append(ab[0])
n_set -= ab[0]

for i in range(1,m-1):
    n_set -= ab[i]
    for j in range(len(bubun)):
        if not ab[i].isdisjoint(bubun[j]):
            bubun[j] |= ab[i]
        else:
            bubun.append(ab[i])

size_old = len(bubun)
while True:
    for i in range(len(bubun)):
        for j in range(i+1, len(bubun)):
            if not bubun[i].isdisjoint(bubun[j]):
                bubun[i] |= bubun[j]
                del bubun[j]

    if len(bubun) != size_old:
        size_old = len(bubun)
        countinue
    else:
        break

print(len(n_set) + len(bubun) - 1)

Submission status: Time Limit Exceeded

Solution code:
numbers = list(map(int, input().split()))
# N...街の数
# M...道路の数
N = numbers[0]
M = numbers[1]
c1 = [0] * M
c2 = [0] * M
citys = []
groups = []

for i in range(N):
    citys.append(i)
    groups.append([])
    groups[i].append(i)

for i in range(M):
    c1[i], c2[i] = map(int, input().split())

for i in range(M):
    f = 0
    s = 0
    for j in range(len(groups)):
        if c1[i] in groups[j]:
            f = j
        if c2[i] in groups[j]:
            s = j
    a = groups[f]
    for i in a:
        groups[s].append(i)
    del groups[f]


print(len(groups) - 1)

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)

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

N, M = map(int, input().split())
array = [[0]*N for _ in range(N)]
for _ in range(M):
    A, B = map(int, stdin.readline().split())
    array[A-1][B-1] = 1

ans = 0
for i in range(1, N):
    ct = 0
    for j in range(0, i):
        ct += array[j][i]
    if ct == 0:
        ans += 1

print(ans)

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] = [i]
 
for i in range(m):
  a, b = map(int, input().split())
  if linked[a] == linked[b]: continue
  linked[a].extend(linked[b])
  for t in linked[b]:
    linked[t] = linked[a]
 
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:
def MII(): return map(int, input().split())

n,m=MII()
groups=[[1]]
group_set=set([1])

for i in range(m):
    a,b=MII()
    a_place=0
    b_place=0
    tmp=[]
    if a in group_set:
        if b in group_set:
            for j,group in enumerate(groups):
                if a in group:
                    a_place=j
                if b in group:
                    b_place=j
                if a_place>0 and b_place>0:
                    break
            if a_place!=b_place:
                tmp=groups[b_place]
                groups[a_place]+=tmp
                del groups[b_place]
        else:
            for group in groups:
                if a in group:
                    group+=[b]
                    group_set.add(b)
                    break
    elif b in group_set:
        for group in groups:
            if b in group:
                group+=[a]
                group_set.add(a)
                break
    else:
        groups+=[[a,b]]
        group_set.add(a)
        group_set.add(b)

print(len(groups)+(n-len(group_set))-1)

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 uf.parents:
	if i < 0:
		ans+=1
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx
# import matplotlib.pyplot as plt
N,M = list(map(int,input().split()))
AB=[list(map(int, input().split())) for i in range(M)]

G=nx.Graph()
G.add_nodes_from(range(1,N+1))
G.add_edges_from(AB)

count=0

nodes=set(range(1,N+1))
p_ori=list(nodes)[0]
reachable=nx.shortest_path(G,p_ori).keys()
nodes-=set(reachable)
while nodes!=set():
    p=list(nodes)[0]
    reachable=nx.shortest_path(G,p).keys()
    nodes-=set(reachable)
    G.add_edge(p,p_ori)
    count+=1
    
print(count)
# nx.draw_networkx(G)

# plt.show()

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]:
            index = j
            # 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]])
    else:
        group[index].append(x[i])
        group[index].append(y[i])

NOs = []
for i in range(N):
    bo = True
    for j in range(len(group)):
        if i in group[j]:
            bo = False
            break
    if bo:
        NOs.append(i)

print(len(group)-1 + len(NOs))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
dic = {x:set([x]) 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)

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

print(count)

Submission status: Time Limit Exceeded

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

a=[list(map(int,input().split())) for i in range(m)]

b=list(itertools.chain.from_iterable(a)) 

c=set(b)
d=list(c)

cnt=0
for i in d:
    if b.count(i)>1:
        cnt+=1

e=n-m-1

if cnt>2:
    f=cnt-2
else:
    f=0

print(e+f)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
s=[]
for _ in range(m):
    a,b=map(int,input().split())
    s.append([a,b])
u=[]
for i in range(0,m-1):
    for j in range(i,m):
        if s[i][0]==s[j][0]:
            u.append([s[i][1],s[j][1]])
t=0            
for i in range(len(u)):
    q=u[i][0]
    w=u[i][1]
    if q>w:
        u[i][0]=w
        u[i][1]=q

for j in u:
    for l in s:
        if j==l:
            t=t+1
print(n-1-m+t)

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]:
            index = j
            # if my_index(group[j], x[i]) != -1:
            #     index = group.index(x[i])
            # else:
            #     index = group.index(y[i])
            bo = False
    if bo:
        group.append([x[i], y[i]])
    else:
        group[index].append(x[i])
        group[index].append(y[i])

NOs = []
for i in range(N):
    bo = True
    for j in range(len(group)):
        if i in group[j]:
            bo = False
    if bo:
        NOs.append(i)

print(len(group)-1 + len(NOs))

Submission status: Time Limit Exceeded

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

num = []

for i in range(N):
    num.append(i + 1)

for i in range(M):
    a, b = map(int, input().split())
    if a in num:
        num.remove(a)
    if b in num:
        num.remove(b)

if M < N:
    print(N - M - 1)
else:
    print(len(num))

Submission status: Time Limit Exceeded

Solution code:
def MII(): return map(int, input().split())
def MSI(): return map(str, input().split())

n,m=MII()
groups=[["1"]]
group_set=set(["1"])

for i in range(m):
    a,b=MSI()
    a_place=0
    b_place=0
    tmp=[]
    if a in group_set:
        if b in group_set:
            for j,group in enumerate(groups):
                if a in group:
                    a_place=j
                if b in group:
                    b_place=j
                if a_place>0 and b_place>0:
                    break
            if a_place!=b_place:
                tmp=groups[b_place]
                groups[a_place]+=tmp
                del groups[b_place]
        else:
            for group in groups:
                if a in group:
                    group+=[b]
                    group_set.add(b)
                    continue
    elif b in group_set:
        for group in groups:
            if b in group:
                group+=[a]
                group_set.add(a)
                continue
    else:
        groups+=[[a,b]]
        group_set.add(a)
        group_set.add(b)

print(len(groups)+(n-len(group_set))-1)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
L=[]
s=N-1
for i in range(M):
    A,B=map(int,input().split())
    if A not in L and B not in L:
        s-=1
    L.append(B)
print(s)

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())
A=[0]*M
B=[0]*M
for i in range(M):
    A[i],B[i]=map(int,input().split())

uf=UnionFind(N+1)
for i in range(M):
    uf.union(A[i],B[i])
    #print(uf.find(1))
#print()
a=[0]*N
#print(uf)
print(len(list(uf.all_group_members().values()))-2)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m = map(int, input().split())
a = [list(map(int,input().split())) for i in range(m)]

ans = 0

c = list(itertools.chain.from_iterable(a))

l = [0] * n
for i in range(n):
  l[i] = c.count(i+1)

#存在しないルート
ans += l.count(0)

#独立したルート
d = [[0]*2 for _ in range(m)]

for i in range(m):
  if l[a[i][0]-1] > 1:
    d[i][0] = 1
  if l[a[i][1]-1] > 1:
    d[i][1] = 1

ans += d.count([0,0])-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx
# import matplotlib.pyplot as plt
N,M = list(map(int,input().split()))
AB=[list(map(int, input().split())) for i in range(M)]

G=nx.Graph()
for i in range(1,N+1):
    G.add_node(i)
for ab in AB:
    G.add_edge(ab[0],ab[1])

count=0

nodes=set(range(1,N+1))
p_ori=list(nodes)[0]
reachable=nx.shortest_path(G,p_ori).keys()
nodes-=set(reachable)
while nodes!=set():
    p=list(nodes)[0]
    reachable=nx.shortest_path(G,p).keys()
    nodes-=set(reachable)
    G.add_edge(p,p_ori)
    count+=1
    
print(count)
# nx.draw_networkx(G)

# plt.show()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
t = []
s = [-1]*n
stc = []
num = 0
for i in range(n):
    t.append([])
for i in range(m):
    a,b = map(int,input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(n):
    if(s[i] == -1):
        stc = t[i]
        j = 0
        s[i] = num
        while(j < len(stc)):
            if(s[stc[j]] == -1):
                s[stc[j]] = num
                stc = stc + t[stc[j]]
            j += 1
        num += 1
print(num-1)

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
        neighborList = []
        for j in range(m):
            if roads[j][0] == i+1:
                if roads[j][1] == checkpoints[roads[j][1]-1]:
                    checkpoints[i] = i+1
                    canContinue = True
                    break;
                neighborList.append(roads[j][1])
        if canContinue == True:
            continue;
        countMakeRoads += 1
        for k in range(len(neighborList)):
            checkpoints[neighborList[k]-1] = neighborList[k]
print(countMakeRoads)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = [int(x) for x in input().split()]
A = list()
B = list()
for i in range(M):
  a, b = [int(x) for x in input().split()]
  A.append(a)
  B.append(b)
  
def dfs(i, flag):
  Next1 = [B[j] for j in range(M) if(A[j]==(1+i))]
  Next2 = [A[j] for j in range(M) if(B[j]==(1+i))]
  if(len(Next1)!=0):
    for j in range(len(Next1)):
      if(flag[Next1[j]-1]==0):
        flag[Next1[j]-1] = 1
        flag = dfs(Next1[j]-1, flag)
  if(len(Next2)!=0):
    for j in range(len(Next2)):
      if(flag[Next2[j]-1]==0):
        flag[Next2[j]-1] = 1
        flag = dfs(Next2[j]-1, flag)
  return flag

if __name__=='__main__':
  ans = 0
  flag = [0 for _ in range(N)]
  i = 0
  flag[i] = 1
  mada = [i for i in range(N) if(flag[i]==0)]
  while True:    
    flag = dfs(i, flag)
    mada = [i for i in range(N) if(flag[i]==0)]
    if(len(mada) == 0):
      break
    i = mada[0]
    flag[i] = 1
    ans += 1
  print(ans)

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())
edges = [list(map(int, input().split())) for i in range(M)]
#隣接行列の作成
l = [[0 for j in range(N+1)] for i in range(N+1)]
for edge in edges:
    l[edge[0]][edge[1]] = 1
    l[edge[1]][edge[0]] = 1

a = np.array(l)
n, labels = connected_components(a)
print(n-2)

Submission status: Time Limit Exceeded

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

rootedPoints = set()
points = []

for _ in range(M):
  A, B = map(int, input().split())
  rootedPoints.add(A)
  rootedPoints.add(B)
  Aindex = False
  Bindex = False
  for i, ps in enumerate(points):
    if A in ps: Aindex = i
    if B in ps: Bindex = i
  if Aindex==False and Bindex==False:
    points.append({A, B})
  elif Aindex==False:
    points[Bindex].add(A)
  elif Bindex==False:
    points[Aindex].add(B)
  elif Aindex!=Bindex:
    points[Aindex] |= points[Bindex]
    del points[Bindex]
print(len(points)-1+N-len(rootedPoints))

Submission status: Time Limit Exceeded

Solution code:

import numpy as np

from scipy.sparse.csgraph import connected_components

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(cities)
print(n-1)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(x) for x in input().split(' ')]
city_s=set(range(1,N+1))

for j in range(0, M):
    A, B = [int(x) for x in input().split(' ')]
    if j == 0:
        dic={}
        dic[0]=[A,B]
    if j != 0:
        for i in range(len(dic)):
            if A in dic[i]:
                dic[i].append(B)
                break
            elif B in dic[i]:
                dic[i].append(A)
                break
            else:
                if i == len(dic)-1:
                    dic[len(dic)]=[A,B]
        
for i in range(len(dic)):
    city_s=city_s-set(dic[i])
print(len(city_s)+len(dic)-1)