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 numpy as np

N, M = [int(x) for x in input().split()]
Edge = [[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
  a, b = [int(x) for x in input().split()]
  Edge[a-1][b-1] = 1
  Edge[b-1][a-1] = 1
  
def dfs(i, flag):
  for n in range(N):
    if(Edge[i][n]==1 and flag[n]!=1):
      flag[n] = 1
      flag = dfs(n, flag)
      break
  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
N, M= list(map(int, input().split(' ')))
city = set([])
road = set(list(map(int, input().split(' '))))
city = city|road
count = 0
for i in range(M-1):
    road = set(list(map(int, input().split(' '))))
    if (len(road&city)==0):
        count = count+1
    city = city|road
isolated = N - len(city)
result = count + isolated
print(result)

Submission status: Time Limit Exceeded

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

dp = [[0 for i in range(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 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=list(range(1,N+1))
p_ori=nodes[0]
reachable=nx.shortest_path(G,p_ori).keys()
nodes=[a for a in nodes if a not in reachable]
while nodes!=[]:
    p=nodes[0]
    reachable=nx.shortest_path(G,p).keys()
    nodes=[a for a in nodes if a not in reachable]
    G.add_edge(p,p_ori)
    count+=1
    
print(count)
# nx.draw_networkx(G)

# plt.show()

Submission status: Time Limit Exceeded

Solution code:
from numba import jit
N, M = map(int, input().split())
def func(N, M):
  group = []
  tf = []
  for i in range(M):
    A, B = map(int, input().split())
    if A not in tf and B not in tf:
      tf.append(A)
      tf.append(B)
      group.append([A,B])
    else:
      if A in tf and B in tf:
        a, b = 0, 0
        for j in range(len(group)):
          if A in group[j]:
            a = j
            if b!=0:
              break
          elif B in group[j]:
            b = j
            if a!=0:
              break
        group[a].extend(group[b])
        del group[b]
      elif A not in tf:
        tf.append(A)
        for j in range(len(group)):
          if B in group[j]:
            group[j].append(A)
            break
      elif B not in tf:
        tf.append(B)
        for j in range(len(group)):
          if A in group[j]:
            group[j].append(B)
            break
  num = N - len(tf) 
  return len(group)+num-1
print(func(N,M))

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 = {}
no_connection = [n + 1 for n in range(N)]

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

Submission status: Time Limit Exceeded

Solution code:
"""
N：都市の数
M:双方向道路の数
"""


class DisjointSet:
    def __init__(self, size):
        self.rank = [0] * size  # rank[x]：ノードxを木の親としたときの木の高さ
        self.p = [0] * size  # p[x]：ノードxの親

        for i in range(N):
            self.p[i] = i  # 自分自身を親
            self.rank[i] = 0  # 最初は自分だけなので木の高さは0

    def same(self, x, y):  # xとyが同じ集合に属しているのかどうかを確認
        return (self.findSet(x) == self.findSet(y))

    def unite(self, x, y):  # 結合
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x_root, y_root):  # x_root(y_root):x(y)が属する集合の親
        if (self.rank[x_root] > self.rank[y_root]):
            self.p[y_root] = x_root
        else:
            self.p[x_root] = y_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[y_root] += 1

    def findSet(self, x):  # xが属する集合の親を返す
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])

        return self.p[x]


N, M = map(int, input().split())
ds = DisjointSet(N)
parents = []

for _ in range(M):
    A, B = map(int, input().split())
    ds.unite(A-1, B-1)  # 都市Aと要素Bを結合

for i in range(N):
    parent = ds.findSet(i)

    if parent not in parents:
        parents.append(parent)

print(len(parents)-1)

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())
if __name__ == '__main__':
    n, m = map(int, input().split())
    uf = UnionFind(n)
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        uf.union(a, b)

    print(len(list(uf.all_group_members().values()))-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = [int(x) for x in input().split()]
Edge = [[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
  a, b = [int(x) for x in input().split()]
  Edge[a-1][b-1] = 1
  Edge[b-1][a-1] = 1
  
def dfs(i, flag):
  for n in range(N):
    if(Edge[i][n]==1 and flag[n]!=1):
      flag[n] = 1
      flag = dfs(n, 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
N, M= list(map(int, input().split(' ')))
city = []
road = list(map(int, input().split(' ')))
count = 0
for i in range(2):
    city = city + road
city = set(city)
for i in range(M-1):
    road = set(list(map(int, input().split(' '))))
    if (len(road&city)==0):
        count = count+1
    city = city|road
isolated = N - len(set(city))
result = count + isolated
print(result)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
vs = []
c = 0
for i in range(m):
	x, y = map(int, input().split())
	f = 0
	for j in range(len(vs)):
		if x in vs[j] or y in vs[j]:
			vs[j].add(x)
			vs[j].add(y)
			f = 1
	if f == 0:
		s = set((x, y))
		vs.append(s)
for i in range(len(vs)):
	c = c + len(vs[i])
print(len(vs) + n - c - 1)

Submission status: Time Limit Exceeded

Solution code:
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:
N, M = map(int, input().split())
AB = [map(int, input().split(' ')) for _ in range(M)]
A, B = [list(i) for i in zip(*AB)]
roads = [[0 for i in range(N)] for j in range(N)]
for a, b in zip(A, B):
    roads[a - 1][b - 1] = 1
    roads[b - 1][a - 1] = 1
print(roads.count([0 for i in range(N)]))

Submission status: Time Limit Exceeded

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

for i in range(M):
  A, B = map(int, input().split())
  if A not in tf and B not in tf:
    tf.append(A)
    tf.append(B)
    group.append([A,B])
  else:
    if A in tf and B in tf:
      a, b = 0, 0
      for j in range(len(group)):
        if A in group[j]:
          a = j
          if b!=0:
            break
        elif B in group[j]:
          b = j
          if a!=0:
            break
      group[a].extend(group[b])
      del group[b]
    elif A not in tf:
      tf.append(A)
      for j in range(len(group)):
        if B in group[j]:
          group[j].append(A)
          break
    elif B not in tf:
      tf.append(B)
      for j in range(len(group)):
        if A in group[j]:
          group[j].append(B)
          break
num = N - len(tf) 
print(len(group)+num-1)

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())
  linked[a] |= linked[b]

  linked[b] = linked[a]
  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:
N = 100000
g = [[] for i in range(N)] 
  
# To check if the vertex  
# has been visited or not 
vis = [False for i in range(N)] 
  
# To store if vertex is reachable 
# from source or not 
good = [False for i in range(N)] 
  
def ADD_EDGE(u, v): 
  
    g[u].append(v) 
  
# Function to find all good vertices 
def dfs1(v): 
  
    good[v] = True
    for to in g[v]: 
        if not good[to]: 
            dfs1(to) 
  
# Function to find cnt of 
# all unreachable vertices 
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) 
  
# Function to return   
# the minimum edges required 
def Minimum_Edges(): 
  
    global vis, cnt 
      
    # Find all vertices reachable 
    # from the source 
    dfs1(x) 
  
    # To store all vertices  
    # with their cnt value 
    val = [] 
  
    for i in range(0, n):  
  
        # If vertex is bad i.e. not reachable 
        if not good[i]: 
            cnt = 0
            vis = [False for i in range(N)] 
  
            # Find cnt of this vertex 
            dfs2(i) 
            val.append((cnt, i)) 
  
    # Sort all unreachable vertices  
    # in non-decreasing order of 
    # their cnt values 
    val.sort(reverse = True) 
  
    # Find the minimum number of edges 
    # needed to be added 
    ans = 0
    for it in val:  
        if not good[it[1]]:  
            ans += 1
            dfs1(it[1]) 
  
    return ans 
  
# Driver code 
if __name__ == "__main__": 
  
    # Number of nodes and source node 
    n, m = map(int, input().split())
    x = 0
  
    # Add edges to the graph
    for i in range(m):
        u, v = map(int, input().split())
        ADD_EDGE(u, v)
  
    print(Minimum_Edges())

Submission status: Time Limit Exceeded

Solution code:
# スペース区切りの整数の入力
N, M = map(int, input().split())
C = []
for i in range(M):
    #内包表記
    b, c = map(int, input().split())
    C.append(b)
    C.append(c)
counts = 0
for p in range(N):
   if p+1 not in C:
    counts += 1
    C.append(p+1)
print(counts)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M= list(map(int, input().split(' ')))
city = []
road = list(map(int, input().split(' ')))
count = 0
for i in range(2):
    city = city + road
for i in range(M-1):
    road = list(map(int, input().split(' ')))
    if (len(set(road)&set(city))==0):
        count = count+1
    city = city + road
isolated = N - len(set(city))
result = count + isolated
print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

cluster=[]
for i in range(m):
    for j in range(len(cluster)):
        if x[i][0] in cluster[j]:
            if x[i][1] in cluster[j]:
                break
            else:
                cluster[j].append(x[i][1])
                break
    
        elif x[i][1] in cluster[j]:
            if x[i][1] in cluster[j]:
                break
            else:
                cluster[j].append(x[i][0])
                break
    
    else:
        cluster.append(x[i])
    continue
    
ans=len(cluster)-1+add_times
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
from collections import Counter
setrecursionlimit(1000000)
def l_in(type_): return list(map(type_, input().split()))
def i_in(): return int(input())
def m_in(type_): return map(type_, input().split())
def r_in(n, type_): return [type_(input()) for _ in range(n)]

def find_components(n, connectors):
    nodes = [i for i in range(n)]
    for a, b in connectors:
        for e in range(n):
            if nodes[e] == nodes[a-1]: nodes[e] = nodes[b-1]
    return len(Counter(nodes))

n, m = m_in(int)
ab = [list(m_in(int)) for _ in range(m)]

ans = find_components(n, ab) - 1

print(ans)

Submission status: Time Limit Exceeded

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

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

cities = [0] * 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]
    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:
N,M = map(int,input().split())
tem = []

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


kosuu = 0

for i in range(len(tem)):
    kosuu += len(tem[i])

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

Submission status: Time Limit Exceeded

Solution code:

n, m = (int(x) for x in input().split())

# 0 = つながりなし, 1 = つながりあり, 2 = つながりあるがチェック済
r_list = [[0 for _ in range(n)] for _ in range(n)]

for i in range(m):
    query = list(map(int, input().split()))
    r_list[query[0] - 1][query[1] - 1] = 1

# print(r_list)

ans = 0

# 最後の都市を覗き都市 - 1だけ確認
for j in range(n - 1):

    root_is_exist = False

    # 各都市とのつながりを確認
    for k in range(n) :
        if r_list[j][k] == 1 :
            root_is_exist = True
            r_list[k][j] = 2

    # 検査の結果1が存在しない場合、ルートを作る
    if root_is_exist == False :
        ans += 1
        # for l in range(n) :
            
        #     # 自分自身の都市でなく、相手もチェックでない道を作る
        #     if 

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f(p,s):
  p2 = float("inf")
  while p != p2:
    q = []
    for i in p:
      q = q+[j[1] for j in s if j[0]==i and j[1] not in p]
    p2 = p
    p = p+q
  return p
n,m = map(int, input().split())
s = []
for i in range(m):
  a,b = map(int, input().split())
  s.append((a,b))
  s.append((b,a))
t = 1
u = [1]
r = set(list(range(1,n+1)))
c = 0
while u != []:
  p = [t]
  u = list(r-set(f(p,s)))
  if u == []:
    break
  r = set(u)
  t = u[0]
  c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
group = []
tf = []
for i in range(M):
  A, B = map(int, input().split())
  if A not in tf and B not in tf:
    tf.append(A)
    tf.append(B)
    group.append([A,B])
  else:
    if A in tf and B in tf:
      for j in range(len(group)):
        if A in group[j]:
          a = j
        elif B in group[j]:
          b = j
      group[a].extend(group[b])
      del group[b]
    elif A not in tf:
      tf.append(A)
      for j in range(len(group)):
        if B in group[j]:
          group[j].append(A)
          break
    elif B not in tf:
      tf.append(B)
      for j in range(len(group)):
        if A in group[j]:
          group[j].append(B)
          break

l = list(range(1,N+1))
for i in tf:
  if i in l:
    l.remove(i)
    
print(len(group)+len(l)-1)

Submission status: Time Limit Exceeded

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

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

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n,m=input2()
AB=[input_array() for _ in range(m)]
D=[[0]*n for _ in range(n)]

for ab in AB:
	a=ab[0]
	b=ab[1]
	D[a-1][b-1]=1

csr=csr_matrix(D)

ans=connected_components(csr, return_labels=False) -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]
    X=list(map(int,input().split()))
    N=X[0]
    M=X[1]
    AB=[list(map(int,input().split())) for _ in range(M)]
    setori=[set(AB[0])]
    kazu=set(AB[0])
    for x in AB:
        kazu.union(set(x))
        for y in setori:
            if y.isdisjoint(set(x)):
                setori.append(set(x))
            else:
                y.union(set(x))
    print(int(N-len(kazu)+len(setori)-1))

if __name__ == '__main__':
    main()

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 = []
    for i, c in enumerate(clusters):
        if s in c:
            merge_ids.append((i, s))
        if t in c:
            merge_ids.append((i, t))

    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:
from collections import deque

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

cnt = 0
for i in l:
    c = len(i)
    if cnt < c:
        cnt = c

ans = 0

def search(s,g):
    global ans
    dist = [-1]*(n)
    dist[s] = 0
    d = deque()
    d.append(s)
    while d:
        v = d.popleft()
        if len(l[v]) >= 1:
            for i in l[v]:
                if dist[i] == -1:
                    dist[i] = dist[v]+1
                    d.append(i)
    if dist[g] == -1:
        ans += 1

for i in range(n):
    search(i,cnt)

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

arr = [ 0 for x in range ( N + 1) ] ;


c = 1 ;
d1 = {} ;
for x in range ( M ) :
	a , b  =  map ( int , input().strip().split(" ") ) ;

	if arr[a] == 0 and arr[b] == 0 :
		arr[a] = c ; 
		arr[b] = c ; 

		L = [] ;
		L.append ( a ) ;
		L.append ( b ) ;
		d1 [ c ] = L ;
		c += 1 ;
	elif arr[a] != 0 and arr[b] == 0 :
		arr[b] = arr[a] ;
		d1[arr[a]].append( b ) ;
	elif arr[a] == 0 and arr[b] != 0 :
		arr[a] = arr[b] ;
		d1[arr[b]].append( a ) ;
	elif arr[a] == arr[b] :
		continue ;
	else :
		rr = arr[b] ;
		for y in d1[rr] :
			d1[arr[a]].append ( y ) ;
			arr[y] = arr[a] ;
		del d1[rr] ;


c = max ( arr ) ;
for x in range ( 1 , N + 1 ) :
	if arr[x] != 0 : continue ;
	c += 1  ;
	arr [x] = c ;
r = set( arr ) ; 



print ( len( r ) -2 ) ;

Submission status: Time Limit Exceeded

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

visited = []
count = -1

for i in range(m):

  x,y = list(map(int, input().split()))

  if x not in set(visited) and y not in set(visited):
    count += 1

  visited.append(x)
  visited.append(y)

visited = set(visited)
count += n - len(visited)
print(count)

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)]
ans=0

l=[-1]*n

def rootfind(a):
    while 1:
        if l[a-1]>0:
            a=l[a-1]
        else:
            break
    return a


def rootunion(c,d):
    cr=rootfind(c)
    dr=rootfind(d)
    if cr==dr:
        pass
    else:
        l[cr-1]=dr


for j in range(m):
    p=x[j]
    q=y[j]
    rootunion(p,q)

for o in l:
    if o<0:
        ans+=1

print(ans-1)

Submission status: Time Limit Exceeded

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

tojo=[]
group=[]
for i in range(m):
  a,b=map(int,input().split())
  if (not a in tojo) and (not b in tojo):
    tojo.append(a)
    tojo.append(b)
    group.append([a,b])
  elif (not a in tojo) and (b in tojo):
    tojo.append(a)
    for j in range(len(group)):
      if b in group[j]:
        group[j].append(a)
        break
  elif (a in tojo) and (not b in tojo):
    tojo.append(b)
    for j in range(len(group)):
      if a in group[j]:
        group[j].append(b)
        break
  else:
    for j in range(len(group)):
      if a in group[j]:
        g1=group.pop(j)
        break
    for j in range(len(group)):
      if b in group[j]:
        group[j]=list(group[j])+list(g1)
        break

road=len(group)-1+n-len(tojo)
print(road)

Submission status: Time Limit Exceeded

Solution code:
import collections
n, m = map(int, input().split())
linked = collections.defaultdict(set)

for i in range(m):
  a, b = map(int, input().split())
  linked[a].add(a)
  linked[b].add(b)
  linked[a] |= linked[b]

  linked[b] = linked[a]
  for t in linked[b]:
    linked[t] = linked[a]
all = set()
groups = set()
for s in linked.values():
  if s:
    groups.add(tuple(s))
    all |= s
    s.clear()
print((n - len(all)) + (len(groups) - 1))

Submission status: Time Limit Exceeded

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

  rootGroups = []

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

    flag = False
    for j in range(len(rootGroups)):
      now = rootGroups[j]
      if a in now:
        now.append(b)
        flag = True
      if b in now:
        now.append(a)
        flag = True
    if not flag:
      rootGroups.append([a, b])

  for i in range(len(rootGroups)):
    rootGroups[i] = list(dict.fromkeys(rootGroups[i]))

  count = 0

  for v in rootGroups:
    count += len(v)


  print((len(rootGroups) - 1) + (n - count))

main()

Submission status: Time Limit Exceeded

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

rootGroups = []

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

  flag = False
  for j in range(len(rootGroups)):
    if a in rootGroups[j]:
      rootGroups[j].append(b)
      flag = True
    if b in rootGroups[j]:
      rootGroups[j].append(a)
      flag = True
  if not flag:
    rootGroups.append([a, b])

result = []

for i in range(len(rootGroups)):
  rootGroups[i] = list(dict.fromkeys(rootGroups[i]))

count = 0
for v in rootGroups:
  count += len(v)


print((len(rootGroups) - 1) + (n - count))

Submission status: Time Limit Exceeded

Solution code:
import collections

N, M = map(int, input().split())
lst = [0] * N
x = 1
for _ in range(M):
  A, B = map(int, input().split())
  if lst[A-1] == 0 and lst[B-1] == 0:
    lst[A-1] = x
    lst[B-1] = x
    x += 1
  elif lst[A-1] == 0 and lst[B-1] != 0:
    lst[A-1] = lst[B-1]
  elif lst[A-1] != 0 and lst[B-1] == 0:
    lst[B-1] = lst[A-1]
  else:
    y = max(lst[A-1], lst[B-1])
    z = min(lst[A-1], lst[B-1])
    for i in range(N):
      if lst[i] == z:
        lst[i] = y
  
c = collections.Counter(lst)

num_0 = c[0]
if num_0 == 0:  
  print(len(c) - 1)
else:
  print(num_0 + len(c) - 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())
g = csr_matrix((n,n),dtype=int)
for i in range(m):
    ai,bi = map(int,input().split())
    g[ai-1,bi-1] = 1
    g[bi-1,ai-1] = 1
r = connected_components(g,return_labels=False)
print(r-1)

Submission status: Time Limit Exceeded

Solution code:
import sys,io,os
I = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
#I = input

n,m = map(int, I().split())
p=[-1]*(n+1)
s=[0]*(n+1)
S=n-1
def t(a):
	while p[a] != -1:
		a = p[a]
	return a
for _ in range(m):
	a,b=map(int, I().split())
	a,b = t(a), t(b)
	if a != b:
		S -= 1
		if s[a] > s[b]:
			a,b = b,a
		p[a] = b
		s[b] += s[a]
print(S)

Submission status: Time Limit Exceeded

Solution code:
n,m = list(map(int,input().split()))
res = [[x] for x in range(1,n+1)]
for _ in range(m):
  i,j = list(map(int,input().split()))
  y,z = None,None
  for x in res:
    if i in x or j in x:
      if y == None:
        y = x
        if j in x:
          break
      else:
        z = x
        res.remove(y)
        res.remove(z)
        res.append(y+z)
        break
print(len(res)-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())
l = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
  _a, _b = map(int, input().split())
  l[_a - 1][_b - 1] = 1

l = np.array(l)
csr = csr_matrix(l)

print(connected_components(csr, return_labels=False) - 1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
groups = []
flag = [0 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    temp = {a, b}
    if flag[a-1] == 1 or flag[b-1] == 1:
        for j in range(len(groups)):
            if temp & groups[j]:
                groups[j] |= temp
    else:
        groups.append(temp)
    flag[a-1] = 1
    flag[b-1] = 1

print(len(groups)+flag.count(0)-1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
mat=[[0]*n for i in range(n)]
for i in range(n):
    mat[i][i]=1
l=[]
for i in range(m):
    x,y=map(int,input().split())
    mat[x-1][y-1]=1
    mat[y-1][x-1]=1
    l.append(x-1)
    l.append(y-1)
out=0
for i in range(n):
    if i not in l:
        out+=1
print(out)

Submission status: Time Limit Exceeded

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

isolated = N
for i in range(M):
  A, B = list(map(int, input().split()))
  if sum(c[A - 1]) == 0 or sum(c[B - 1]) == 0:
    isolated -= 1
  c[A-1][B-1] = 1
  c[B-1][A-1] = 1

print(isolated - 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())
g = [[0]*n for i in range(n)]
for i in range(m):
    ai,bi = map(int,input().split())
    g[ai-1][bi-1] = 1
    g[bi-1][ai-1] = 1
g = csr_matrix(g)
r = connected_components(g,return_labels=False)
print(r-1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

par = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]

def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

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

def unite(x, y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

for a, b in edges:
    unite(a, b)
memo = []
ans = 0
for i in range(1, n + 1):
    if root(i) not in memo:
        memo.append(root(i))
        ans += 1
print(ans - 1)

Submission status: Time Limit Exceeded

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

G=[0 for i in range(n)]
g=1

for i in range(m):
  a,b=map(int,input().split(" "))
  if G[a-1]==0:
    if G[b-1]==0:
      G[a-1]=g
      G[b-1]=g
      g=g+1
    else:
      G[a-1]=G[b-1]
  else:
    if G[b-1]==0:
      G[b-1]=G[a-1]
    else:
      if G[a-1]<=G[b-1]:
        x=G[b-1]
        y=G[a-1]
        G=[i if i!=x else y for i in G]
        
      
    
z=G.count(0)-1

ans=len(set(G))+z
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
na = list(range(1, N))
nb = list(range(2, N+1))
for _ in range(M):
    a, b = map(int, input().split())
    if a in na:
        na.remove(a)
    if b in nb:
        nb.remove(b)
print(min(len(na), len(nb)))