Problem:


Score : 500 points

Problem Statement

There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.

Let A_i be the integer written on the i-th card.

Your objective is to guess A_1, A_2, ..., A_N correctly.

You know the following facts:

For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.

You are a magician and can use the following magic any number of times:

Magic: Choose one card and know the integer A_i written on it. The cost of using this magic is 1.

What is the minimum cost required to determine all of A_1, A_2, ..., A_N?

It is guaranteed that there is no contradiction in given input.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq X_i < Y_i \leq N

1 \leq Z_i \leq 100

The pairs (X_i, Y_i) are distinct.

There is no contradiction in input. (That is, there exist integers A_1, A_2, ..., A_N that satisfy the conditions.)

Input

Input is given from Standard Input in the following format:

N M
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_M Y_M Z_M

Output

Print the minimum total cost required to determine all of A_1, A_2, ..., A_N.

Sample Input 1

3 1
1 2 1

Sample Output 1

2

You can determine all of A_1, A_2, A_3 by using the magic for the first and third cards.

Sample Input 2

6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5

Sample Output 2

2

Sample Input 3

100000 1
1 100000 100

Sample Output 3

99999



Sample input:
3 1
1 2 1


Sample output:
2

Submission status: Runtime Error

Solution code:
import sys
imput = sys.stdin.readline
N,M =map(int,input().split())
adj =[{}for _ in range(N)]
for i in range(M):
    i,j,k = map(int,input().split())
    adj[i][j]=0
    adj[j][i]=0
n = 0
sta =[True for _ in range(N)]
nokori ={i:0 for i in range(N)}
while len(nokori)!=0:
    n += 1
    tsugi =[list(nokori.keys())[0]]
    nokori.pop(tsugi[0])
    while len(tsugi)!=0:
        foo = []
        for i in tsugi:
            for j in adj[i]:
                if sta[j]:
                    sta[j]=False
                    nokori.pop(j)
                    foo.append(j)
                adj[j].pop(i)
            adj[i].clear()
        tsugi =foo
print(n)

Submission status: Runtime Error

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

list = [0]*n
list[s[0][0]] = 1
list[s[0][1]] = 1
list[s[0][2]] = 1
ans = 2

for i in s:
    temp = list[i[0]]+list[i[1]]+list[i[2]]
    if temp==2:
        list[i[0]] = 1
        list[i[1]] = 1
        list[i[2]] = 1

for i in s:
    temp = list[i[0]]+list[i[1]]+list[i[2]]
    if temp==2:
        list[i[0]] = 1
        list[i[1]] = 1
        list[i[2]] = 1

for i in s:
    temp = list[i[0]]+list[i[1]]+list[i[2]]
    if temp==1:
        ans = ans+1
        list[i[0]] = 1
        list[i[1]] = 1
        list[i[2]] = 1

for i in s:
    temp = list[i[0]]+list[i[1]]+list[i[2]]
    if temp==2:
        ans = ans+1
        list[i[0]] = 1
        list[i[1]] = 1
        list[i[2]] = 1
        
for i in s:
    temp = list[i[0]]+list[i[1]]+list[i[2]]
    if temp==0:
        ans = ans+2
        list[i[0]] = 1
        list[i[1]] = 1
        list[i[2]] = 1
for i in s:
    temp = list[i[0]]+list[i[1]]+list[i[2]]
    if temp==2:
        ans = ans+1
        list[i[0]] = 1
        list[i[1]] = 1
        list[i[2]] = 1

print(ans)

Submission status: Runtime Error

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

class UnionFind():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self.parent = [n for n in range(0, N)]
        # グループの深さ
        self.size = [1] * N

    def find(self, x):
        """ 木の根(どのグループか)を求める """
        if self.parent[x] == x: return x
        self.parent[x] = self.find(self.parent[x]) # 縮約
        return self.parent[x]

    def unite(self, x, y):
        """ xとyの属する集合を併合する """
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self.size[gx] < self.size[gy]:
            self.parent[gx] = gy
            self.size[gy] += self.size[gx]
        else:
            self.parent[gy] = gx
            self.size[gx] += self.size[gy]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find(x) == self.find(y)


def solve():
    N, M = list(map(int, input().split()))
    X, Y, Z = [], [], []
    uf = UnionFind(N)
    for i in range(M):
        x, y, z = list(map(int, input().split()))
        x, y = x-1, y-1
        uf.unite(x, y)
    
    # 答えは、(グループの数) 
    ans = 0
    for i in range(N):
        if uf[i].find(i) == i:
            ans += 1
    
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]


n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
uf = UnionFind(n)
for i in a:
    uf.union(i[0],i[1])

print(len(list(set(uf.par))))

Submission status: Runtime Error

Solution code:
import math

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

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

belong=[0 for i in range(n+1)]
belong[0]=-1
cluslist=[]

cluster=0
zeros = n

for i in range(m):
    if(belong[num[i][0]]==0 and belong[num[i][1]]==0):
        cluster+=1
        belong[num[i][0]]=cluster
        belong[num[i][1]]=cluster
        zeros -= 2
        cluslist.append(cluster)
    elif(belong[num[i][0]]==0):
        belong[num[i][0]]=belong[num[i][1]]
        zeros -=1
    elif(belong[num[i][1]]==0):
        belong[num[i][1]]=belong[num[i][0]]
        zeros -=1
    elif(num[i][0]==num[i][1]):
        kk=3+4
    else:
        for j in range(m):
            if(belong[j]==belong[num[i][1]]):
                belong[j]=belong[num[i][0]]
        cluster-=1
        
print(zeros+cluster)

Submission status: Runtime Error

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

groups = []

for _ in range(m):
  a, b, _ = map(int, input().split())
  for i in range(len(groups)):
    if a in group[i]:
      group[i].append(b)
    elif b in group[i]:
      group[i].append(a)
  else:
    groups.append([a,b])

lenSum = 0
for group in groups:
  lenSum += len(group)

# print(groups)

ans = len(groups) + n - lenSum
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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


par=[ i for i 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 x==y: return
	par[x]=y



for i in range(M):
	x,y,z=map(int, raw_input().split())
	unite(x,y)


S=set()
for i in range(1,N+1):
	S.add(root(i))


print len(S)

Submission status: Runtime Error

Solution code:
import numpy as np

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

known_dict = {}
search_count = 0

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

  ary = [np.sort(x[:2]) for x in ary]
  ary = np.array(ary)
  ary = ary[np.argsort(ary[:, 0]), :]
  print(ary)
  for i in range(m):
    w_ary = ary[i]
    if not (w_ary[0] in known_dict or w_ary[1] in known_dict) :
      search_count += 1
      known_dict[w_ary[0]] = "1"
      known_dict[w_ary[1]] = "1"

print(search_count + (n - len(known_dict)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
def search(i, visited, ns) :
    #print(":", i+1)
    visited[i] = True
    for next, weight in ns[i]:
        if visited[next] == False:
            search(next, visited, ns)


def dfs(ns):
    visited = [False] * len(ns)
    ans = 0
    for i in range(len(ns)):
        if not visited[i]:
            #print(i+1)
            ans += 1
            search(i, visited, ns)
    return ans

def main():
    n,m = map(int,input().split())
    ns = [[] for _ in range(n)]
    for _ in range(m):
        (st,end,weight) = map(int,input().split())
        ns[st-1].append((end - 1,weight))
        ns[end-1].append((st-1,weight))
    ans = dfs(ns)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
G=np.zeros((N+1,N+1))
for i in range(M):
    X,Y,Z=map(int,input().split())
    G[i][X]=1
    G[i][Y]=1
    G[i][Z]=1
print(N-np.linalg.matrix_rank(G))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = []
count = 0
for i in range(n):
    a.append([i+1])
for i in range(m):
    x,y,z=map(int,input().split())
    if a[x] == 0:
        a[y] = 0
    else:
        a[x].append(a.pop[y])
        a.insert(y,0)
for i in range(n):
    if a[i] == 0:
        count += 1
print(n-count)

Submission status: Runtime Error

Solution code:
import numpy as np

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

known_dict = {}
search_count = 0

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

  ary = [np.sort(x[:2]) for x in ary]
  ary = np.array(ary)
  ary = ary[np.argsort(ary[:, 0]), :]
  print(ary)
  for i in range(m):
    w_ary = ary[i]
    if not (w_ary[0] in known_dict or w_ary[1] in known_dict) :
      search_count += 1
      known_dict[w_ary[0]] = "1"
      known_dict[w_ary[1]] = "1"

      print(search_count + (n - len(known_dict)))

Submission status: Runtime Error

Solution code:
from io import StringIO
from collections import *
from functools import *
import sys


class Node:

    def __init__(self):
        self.specs = dict() # 'idx: z'
        self.value = None
        pass

    def has_value(self):
        return self.value != None

    def set_value(self, an, value):
        if self.value != None:
            return
        self.value = value
        for idx_str, z in self.specs.items():
            an[int(idx_str)-1].set_value(an, self.__resolve(z))
            pass
        pass

    def __resolve(self, z):
        return 1 if (self.value + z) % 1 else 2

    def set_spec(self, an, xy, z):
        self.specs[str(xy)] = z
        pass

    def __repr__(self):
        return "{}".format((self.specs, self.value))
            

def main(inputs):
    # n = int(next(inputs))
    # xs = list(map(int, next(inputs).split()))
    n, m = map(int, next(inputs).split())
    
    an = [ Node() for _ in range(n) ]
    for x, y, z in  [ list(map(int, next(inputs).split())) for _ in range(m) ]:
        an[x-1].set_spec(an, y, z)
        an[y-1].set_spec(an, x, z)
        pass

    ans = 0
    for a in an:
        if not a.has_value():
            ans += 1
            a.set_value(an, 1)
            pass
        pass

    return ans


def gen_inputs(str_=None):
    inputs = StringIO(str_) if str_ else sys.stdin
    while True:
        a = inputs.readline().rstrip()
        yield a
        pass
    pass


if __name__ == "__main__":
    print(main(gen_inputs()))
    pass

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
      
      
uf = UnionFind()
n, m = map(int,input().split())
for i in range(m):
  x, y, z = map(int,input().split())
  uf.union(x,y)
  
  
a = [0]*n
for i in range(n):
  a[uf.find[i]] += 1
  
print(n-a.count('0'))

Submission status: Runtime Error

Solution code:
def input(): return sys.stdin.readline().strip()
n,m = map(int,input().split())
s = [input().split() for i in range(m)]
li = [[s[0][0],s[0][1]]]
del s[0]
for item in s:
  num_1 = item[0]
  num_2 = item[1]
  for group in li:
    if num_1 in group and num_2 in group:
      flag=0
      pass
      break
    elif num_1 in group:
      group.append(num_2)
      flag=0
      break
    elif num_2 in group:
      group.append(num_1)
      flag=0
      break
    else:
      flag = 1
  if flag:
    li.append([num_1,num_2])
count = 0
for j in li:
  count += len(j)-1
print(n-count)

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

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

a = {}
b = {}
for i in range(M):
  X, Y, Z = [int(i) for i in input().strip().split(' ')]
  if X not in a:
    a[X] = set()
    b[X] = 0
  if Y not in a:
    a[Y] = set()
    b[Y] = 0

  a[X].add(Y)
  b[X] += 1
  a[Y].add(X)
  b[Y] += 1

b = sorted(list(b.items()), key=lambda e: e[1], reverse=True)

def make_keys(keys, key):
  if key in keys:
    return
  keys.add(key)
  if key in a:
    for k in a[key]:
      make_keys(keys, k)


counter = 0
# print(b)
for key, v in b:
  if key not in a:
    continue
  keys = set()
  make_keys(keys, key)

  for k in keys:
    if k in a:
      del a[k]

  counter += 1

print(counter + N - len(b))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
checked = [False for i in range(n)]
lnk = [set() for i in range(n)]
ans = 0

def mtd(i):
    if len(lnk[i]) == 0 or checked[i]:
        return False
    
    checked[i] = True
    for j in lnk[i]:
    	if not checked[j]:
            mtd(j)
            checked[j] = True
    return True

for i in range(m):
    _x, _y, _z = map(int, input().split())
    lnk[_x - 1].add(_y - 1)
    lnk[_y - 1].add(_x - 1)

for i in range(n):
    if not checked[i] and mtd(i):
        ans += 1

for i in range(n):
    if not checked[i]:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input()) 
l = int(input()) 
m=[]
for i in range(l):
    m.append(map(int, input().split()))
f = [0]*n
for i in range(l):
    if m[i][2]%2==0:
        f[m[i][0]]=2
        f[m[i][1]]=2
print(len([i for i in f if i ==0]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

known_dict = {}
search_count = 0

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

ary = [np.sort(x[:2]) for x in ary]
ary = np.array(ary)
ary = ary[np.argsort(ary[:, 0]), :]
print(ary)
for i in range(m):
  if not (w_ary[0] in known_dict or w_ary[1] in known_dict) :
    search_count += 1
  known_dict[w_ary[0]] = "1"
  known_dict[w_ary[1]] = "1"

print(search_count + (n - len(known_dict)))

Submission status: Runtime Error

Solution code:
import math

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

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

belong=[0 for i in range(n+1)]
belong[0]=-1
cluslist=[]

cluster=0
zeros = n

for i in range(m):
    if(belong[num[i][0]]==0 and belong[num[i][1]]==0):
        cluster+=1
        belong[num[i][0]]=cluster
        belong[num[i][1]]=cluster
        zeros -= 2
        cluslist.append(cluster)
    elif(belong[num[i][0]]==0):
        belong[num[i][0]]=belong[num[i][1]]
        zeros -=1
    elif(belong[num[i][1]]==0):
        belong[num[i][1]]=belong[num[i][0]]
        zeros -=1
    elif(num[i][0]==num[i][1]):
        kk=3+4
    else:
        for j in range(m):
            if(belong[j]==belong[num[i][1]]):
                belong[j]=belong[num[i][0]]
        
print(zeros+cluster)

Submission status: Runtime Error

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

a = {}
b = {}
for i in range(M):
  X, Y, Z = [int(i) for i in input().strip().split(' ')]
  if X not in a:
    a[X] = set()
    b[X] = 0
  if Y not in a:
    a[Y] = set()
    b[Y] = 0

  a[X].add(Y)
  b[X] += 1
  a[Y].add(X)
  b[Y] += 1


def make_keys(keys, key):
  if key in keys:
    return
  keys.add(key)
  if key in a:
    for k in a[key]:
      make_keys(keys, k)


counter = 0
# print(b)
for key, v in b:
  if key not in a:
    continue
  keys = set()
  make_keys(keys, key)

  for k in keys:
    if k in a:
      del a[k]

  counter += 1

print(counter + N - len(b))

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int, input().split())
arr= np.zeros((m, n), dtype=np.int8)
for i in range(m):
  x, y, z = map(int, input().split())
  arr[i, x-1] = 1
  arr[i, y-1] = -1

rank = np.linalg.matrix_rank(arr)
print(n-rank)

Submission status: Runtime Error

Solution code:
from io import StringIO
from collections import *
from functools import *
import sys


class Node:

    def __init__(self):
        self.specs = dict() # 'idx: z'
        self.value = None
        pass

    def has_value(self):
        return self.value != None

    def set_value(self, an, value):
        if self.value != None:
            return
        self.value = value
        for idx_str, z in self.specs.items():
            an[int(idx_str)-1].set_value(an, self.__resolve(z))
            pass
        pass

    def __resolve(self, z):
        return 1 if (self.value + z) % 1 else 2

    def set_spec(self, an, xy, z):
        if self.has_value():
            an[xy-1].set_value(an, self.__resolve(z))
            self.__tx(an, xy, z)
        elif an[xy-1].has_value():
            self.set_value(an, an[xy-1].__resolve(z))
        else:
            self.specs[str(xy)] = z
            pass
        pass

    def __repr__(self):
        return "{}".format((self.specs, self.value))
            

def main(inputs):
    # n = int(next(inputs))
    # xs = list(map(int, next(inputs).split()))
    n, m = map(int, next(inputs).split())
    
    an = [ Node() for _ in range(n) ]
    for x, y, z in  [ list(map(int, next(inputs).split())) for _ in range(m) ]:
        an[x-1].set_spec(an, y, z)
        an[y-1].set_spec(an, x, z)
        pass

    ans = 0
    for a in an:
        if not a.has_value():
            ans += 1
            a.set_value(an, 1)
            pass
        pass

    return ans


def gen_inputs(str_=None):
    inputs = StringIO(str_) if str_ else sys.stdin
    while True:
        a = inputs.readline().rstrip()
        yield a
        pass
    pass


if __name__ == "__main__":
    print(main(gen_inputs()))
    pass

Submission status: Runtime Error

Solution code:
n,m=maP(int,input().split())
k=[0]*n
mp=0
for i in range(m):
  x,y,z=map(int,input().split())
  if k[x-1]==0 and k[y-1]==0:
    mp+=1
    k[x-1]=1
    k[y-1]=1
  else:
    k[x-1]=1
    k[y-1]=1
print(mp+n-sum(k))

Submission status: Runtime Error

Solution code:


N,M=[int(c) for c in input().split()]



graph_indexes=[i for i in range(N)] #それぞれの数は, どのグラフに含まれているのか
graphs=[[i] for i in range(N)] #実際のグラフ

for i in range(M):
	X,Y,Z=[int(c)-1 for c in input().split()]
	X_i=graph_indexes[X]
	Y_i=graph_indexes[Y]
	if(X_i!=Y_i):
		graphs[X_i].extend(graphs[Y_i].copy())
		for j in graphs[Y_i]:
			graph_indexes[j]=graph_indexes[X]

		graphs[Y_i]=[]
		#graph_indexes[Y]=graph_indexes[X]
		#[0,1,2,3][4,5,6]
		#gi[3]=0

		#[0,1,2,3,4,5,6]
	

i=0
for g in graphs:
	if(g!=[]):
		i+=1
print(i)

Submission status: Runtime Error

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

a = {}
b = {}
for i in range(M):
  X, Y, Z = [int(i) for i in input().strip().split(' ')]
  if X not in a:
    a[X] = set()
    b[X] = 0
  if Y not in a:
    a[Y] = set()
    b[Y] = 0

  a[X].add(Y)
  b[X] += 1
  a[Y].add(X)
  b[Y] += 1


def make_keys(keys, key):
  if key in keys:
    return
  keys.add(key)
  for k in a[key]:
    make_keys(keys, k)


counter = 0
# print(b)
for key, v in b:
  if key not in a:
    continue
  keys = set()
  make_keys(keys, key)

  for k in keys:
    if k in a:
      del a[k]

  counter += 1

print(counter + N - len(b))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)
def func(c,x):
    c[x][0] = 1
    for i in c[x][1:]:
        if c[i][0] == 0:
            func(c,i)
    return c

# 入力
N,M = map(int,input().split())
XYZ = list(list(map(int,input().split()))for i in range(M))
############################################
card = [[0]for i in range(N)]
set = 0
############################################
# グラフを描く
for x,y,z in XYZ:
    card[x-1].append(y-1)
    card[y-1].append(x-1)
############################################
for i in range(N):
    if card[i][0] == 0:
        set += 1
        card = func(card,i)
############################################
print(set)

Submission status: Runtime Error

Solution code:
N,M = (int(i) for i in input().split())
e = [[int(i) for i in input().split()] for i in range(M)]
hoge = set()

zenbu = {int(i + 1) for i in range(N)}
result = 0

for i in e:
    onon = {e[0],e[1]}
    if onon.issubset(hoge) == False:
        result += 1
    hoge.add(e[0])
    hoge.add(e[1])

hoge_difference = zenbu - hoge
result += len(hoge_difference)

print(result)

Submission status: Runtime Error

Solution code:
N,M = (int(i) for i in input().split())
e = [[int(i) for i in input().split()] for i in range(M)]
hoge = set()

zenbu = [int(i + 1) for i in range(N)]
result = 0

for i in e:
    onon = {e[0],e[1]}
    if onon.issubset(hoge) == False:
        result += 1
    hoge.add(e[0])
    hoge.add(e[1])

hoge_difference = zenbu - hoge
result += len(zenbu)

print(result)

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int, input().split())
arr= np.zeros((m, n))
for i in range(m):
  x, y, z = map(int, input().split())
  arr[i, x-1] = 1
  arr[i, y-1] = -1

rank = np.linalg.matrix_rank(arr)
print(n-rank)

Submission status: Runtime Error

Solution code:
from sys import stdin

list = []

class Card():
  def __init__(self,v):
    self.p=0
    self.v=v

  def set_p(self, p):
    if p.p == self.v:
      self.p = self.p
    else:
      self.p = p.get_p()

  def get_p(self):
    if self.p !=0:
      return list[self.p-1].get_p()
    else:
      return self.v

n, m = [int(x) for x in stdin.readline().rstrip().split()]

for i in range(1,n+1):
  list.append(Card(i))

for i in range(m):
  x, y, z = [int(x) for x in stdin.readline().rstrip().split()]
  parent = min(x,y)
  child = max(x,y)
  if( list[child-1].p != 0 ):
    list[parent-1].set_p(list[child-1])
  else:
    list[child-1].set_p(list[parent-1])

ans=0
for i in range(0,n):
  #print(list[i].v, list[i].p)
  if( list[i].p==0):
    ans+=1

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
datalist = [0 for i in range(n)]
ans = 0
root = [[] for i in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    root[x - 1].append(y - 1)
    root[y - 1].append(x - 1)

def solve(now):
    global ans, root
    if datalist[now] == 0:
        ans += 1
    datalist[now] = 1
    for j in range(len(root[now])):
        if not datalist[root[now][j]]:
            datalist[root[now][j]] = 1
            solve(root[now][j])

for i in range(n):
    if not datalist[i]:
        #print(i,i,i)
        solve(i)

for i in datalist:
    if i == 0:
        ans += 1

#print(datalist)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self):
    self.parent = None

  @property
  def root(self):
    if self.parent is not None:
      return self.parent.root
    else:
      return self


def main():
  n, m = map(int, input().split())
  nodes = [Node() for _ in range(n)]
  roots = set(nodes)

  for _ in range(m):
    x, y, _ = map(int, input().split())
    x -= 1
    y -= 1

    if nodes[x].root != nodes[y].root:
      roots.remove(nodes[x].root)
      roots.remove(nodes[y].root)
      root = Node()
      nodes[x].root.parent = root
      nodes[y].root.parent = root
      roots.add(root)

  print(len(roots))


if __name__ == '__main__':
  main()

Submission status: Runtime Error

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

kaisuu = N

while len(xyz) > 0:
    tree = []
    next = []
    now = xyz.pop(0)[0:2]
    flag = True
    while flag:
        flag = False
        for z in now:
            idx = []
            for i in range(len(xyz)):
                x = xyz[i][0]
                y = xyz[i][1]
                if x == z or y == z:
                    idx.append(i)
                    if x not in tree and x not in next and x not in now:
                        next.append(x)
                        flag = True
                    elif y not in tree and y not in next and y not in now:
                        next.append(y)
                        flag = True
            for i in idx:
                xyz.pop(i)
        tree += now
        now = next
    
    kaisuu -= len(tree)-1

print(kaisuu)

Submission status: Runtime Error

Solution code:
n,m=map(int(input().split()))
tree=[[] for i in range(n)]
for i in range(m):
  a=map(int,input().split())
  tree[a[0]-1].append(a[1]-1)
c=[1 for i in range(n)]
ans=0
for i in range(n):
  ans+=c[i]
  for j in tree[i]:
    c[j]=0
print(ans)

Submission status: Runtime Error

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

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


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


for x, y, z in XYZ:
    unite(x, y)
s = set()
for i in range(1, N + 1):
    s.add(find(i))
print(len(set(s)))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
checked = [False for i in range(n)]
ans = 0

def mtd(i):
    if len(lnk[i]) == 0:
        return False
    
    checked[i] = True
    for j in lnk[i]:
    	if not checked[j]:
            checked[j] = True
            mtd(j)
    return True

x = []
y = []

lnk = [set() for i in range(n)]

for i in range(m):
    _x, _y, _z = map(int, input().split())
    x.append(_x)
    y.append(_y)
    lnk[_x - 1].add(_y - 1)
    lnk[_y - 1].add(_x - 1)

for i in range(n):
    if not checked[i] and mtd(i):
        ans += 1

for i in range(n):
    if not checked[i]:
        ans += 1

print(ans)

Submission status: Runtime Error

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

g = [[] for i in range(n+1)]
a = [-1 for i in range(n+1)]

for i in range(m):
  x, y, z = [int(i) for i in input().split()]
  g[x].append(y)
  g[y].append(x)

def dfs(x):
  a[x] = 1
  for i in g[x]:
    if a[i] == -1:
      dfs(i)

ans = 0

for i in range(1, n+1):
  if a[i] == -1:
    ans = ans + 1
    dfs(i)

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
datalist = [0 for i in range(n)]
ans = 0
root = [[] for i in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    root[x - 1].append(y - 1)
    root[y - 1].append(x - 1)

def solve(now, root):
    global ans
    #print(now, ans)
    if datalist[now] == 0:
        ans += 1
    datalist[now] = 1
    for j in range(len(root[now])):
        if datalist[root[now][j]] == 0:
            datalist[root[now][j]] = 1
            solve(root[now][j], root)

for i in range(n):
    if datalist[i] == 0:
        #print(i,i,i)
        solve(i, root)

for i in datalist:
    if i == 0:
        ans += 1

#print(datalist)
print(ans )

Submission status: Runtime Error

Solution code:
list=input().split(" ")
n=int(list[0])
m=int(list[1])

siki=[]

for i in range(m):
    list=input().split(" ")
    a=int(list[0])
    b=int(list[1])
    siki.append([a,b])

#print(siki)
#siki.sort(key=itemgetter(1))
#print(siki)

katamari=[]
katamari.append(siki[0])
dekai=siki[0][1]
nanko=2

siki=siki[1:]

for sk in siki:
    aswitch=0
    bswitch=0
    ais=0
    bis=0
    for kt in katamari:
        if sk[0] in kt:
            aswitch=1
            break
        else:
            ais+=1
    for kt in katamari:
        if sk[1] in kt:
            bswitch=1
            break
        else:
            bis+=1
    if aswitch==0:
        if bswitch==0:
            katamari.append(sk)
            nanko+=2
        else:
            katamari[bis].append(sk[0])
            nanko+=1
    else:
        if bswitch==0:
            katamari[ais].append(sk[1])
            nanko+=1
        else:
            if ais!=bis:
                sho=min(ais, bis)
                dai=max(ais, bis)
                for kd in katamari[dai]:
                    katamari[sho].append(kd)
                if sho+1>=len(ketamari):
                    katamari=katamari[:sho]
                else:
                    katamari=katamari[:sho]+katamari[sho+1:]
#print(katamari)
#print(n-nanko)
print(len(katamari)+n-nanko)

Submission status: Runtime Error

Solution code:
def func(c,x):
    c[x][0] = 1
    for i in c[x][1:]:
        if c[i][0] == 0:
            func(c,i)
    return c

# 入力
N,M = map(int,input().split())
XYZ = list(list(map(int,input().split()))for i in range(M))
############################################
card = [[0]for i in range(N)]
set = 0
############################################
# グラフを描く
for x,y,z in XYZ:
    card[x-1].append(y-1)
    card[y-1].append(x-1)
############################################
for i in range(N):
    if card[i][0] == 0:
        set += 1
        card = func(card,i)
############################################
print(set)

Submission status: Runtime Error

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


class UnionFind():
    def __init__(self, n):
        self.rank = [1 for _ in range(n)]
        self.parent = [i for i in range(n)]

    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if self.rank[i] < self.rank[j]:
            self.parent[i] = j
        else:
            if self.rank[i] == self.rank[j]:
                self.rank[j] += 1
            self.parent[j] = i

    def same(self, i, j):
        return self.root(i) == self.root(j)

    def root(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.root(self.parent[i])
        return self.parent[i]


uf = UnionFind(N)

for _ in range(M):
    X, Y, _ = list(map(int, input().split()))
    uf.union(X-1, Y-1)

ans = 0

for i in range(N):
    if uf.root(i) == i:
        ans += 1

print(ans)