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:
N, M = [int(x) for x in input().split()]

# Union Find
# N = 100
PARENT = list(range(N))

used = set()


def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret


def same(n1, n2):
    return root(n1) == root(n2)


def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2


for i in range(M):
    x, y, z = [int(x) for x in input().split()]
    x -= 1
    y -= 1
    used.add(x)
    used.add(y)
    rootX = root(x)
    rootY = root(y)
    if z % 2 == 0:
        unite(x, y)

cnt = 0
uf = {root(n) for n in used}

ans = (len(uf) + 1) // 2 + (N - len(used))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
X, Y = [], []

# union-find
class UF(object):
    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, v):
        if v == self.parent[v]:
            return v
        else:
            self.parent[v] = self.root(self.parent[v])
            return self.parent[v]
    
    def unite(self, u, v):
        u, v = self.root(u), self.root(v)
        if (u == v):
            return
        self.parent[u] = v

uf = UF(N)
# vertex table
V = [[] for _ in range(N)]
for _ in range(M):
    x, y, z = map(int, input().split())
    uf.unite(x-1, y-1)
    V[x-1].append(y-1)
    V[y-1].append(x-1)

# search connection
visit = [False for _ in range(N)]

def dfs(v, V, visit):
    search = deque()
    # search = []
    visit[v] = True
    search.append(v)
    while len(search) > 0:
        v = search.pop()
        for u in V[v]:
            if not visit[u]:
                visit[u] = True
                search.append(u)
    return visit

con = 0
# while not all(visit):
#     v = visit.index(False)
#     if V[v] != []:
#         visit = dfs(v, V, visit)
#     else:
#         visit[v] = True
#     con += 1

print(len(set(uf.root(x) for x in range(N))))

# print(con)

Submission status: Runtime Error

Solution code:
# unionfind

class UnionFind(object):

    def __init__(self, n):
        self.n = n
        self.parent = list(range(self.n + 1))
        self.rank = [0]*n

    def find_parent(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find_parent(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        xp = self.find_parent(x)
        yp = self.find_parent(y)
        if xp == yp:
            return None
        else:
            self.parent[xp] = yp
            return None


N, M = map(int, input().split())
uf = UnionFind(N+1)

for _ in range(M):
    x, y, z = map(int, input().split())
    uf.unite(x, y)

res = [0] * (N + 1)
res_c = 0
for i in range(1, N + 1):
    j = uf.find_parent(i)
    if res[j] == 0:
        res_c += 1
    res[j] += 1

print(N - (sum(res) - res_c))

Submission status: Runtime Error

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

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

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if i < j:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

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


###############################################################################


def main():
    n, m = intin()
    xyzlist = intinl(m)

    u = UnionFind(n)
    for x, y, z in xyzlist:
        u.unite(x - 1, y - 1)

    ansset = set()
    for i in range(n):
        ansset.add(u.root(i))

    return

    print(len(ansset))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

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

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if i < j:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

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


###############################################################################


def main():
    n, m = intin()
    xyzlist = intinl(m)

    u = UnionFind(n)
    for x, y, z in xyzlist:
        u.unite(x - 1, y - 1)

  return

    ansset = set()
    for i in range(n):
        ansset.add(u.root(i))

    print(len(ansset))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

z = x.extend(y)
N = range(n)
for i in range(n):
    N[i] = z.count(i+1)

ans = 0
for i in range(n):
    ans = ans + N.count(i)/(2**i)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

N, M = list(map(int, input().split()))
node2set_id = defaultdict(int)
set_id2nodes = defaultdict(set)

# idxなどを振る
id_left = [i + 1 for i in range(M)]

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

    # ともにIDが振られていないとき
    if node2set_id[x] + node2set_id[y] == 0:
        id = id_left.pop()
        # x,yが所属するグループIDを振る
        node2set_id[x] = id
        node2set_id[y] = id

        # グループIDに対するセットを追加
        set_id2nodes[id] |= {x, y}

    # どちらか一方にのみIDが振られているとき(片方が0になる)
    elif node2set_id[x] * node2set_id[y] == 0:
        id = node2set_id[x] + node2set_id[y]
        node2set_id[x] = id
        node2set_id[y] = id
        set_id2nodes[id] |= {x, y}

    # 両方振られているとき
    else:
        # 同じIDならそもそも考える必要がない
        if node2set_id[x] - node2set_id[y] == 0:
            continue

        # 異なるグループのときにはマージする
        id = node2set_id[x]
        prev_y = y

        # yが所属するグループIDをすべてxのものに置き換える
        for y_idx in set_id2nodes[node2set_id[y]]:
            node2set_id[y_idx] = id
            set_id2nodes[id] |= {y_idx}
        del set_id2nodes[prev_y]

num = sum([len(m)-1 for m in set_id2nodes.values()])

print(N-num)

Submission status: Runtime Error

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

z = x.extend(y)
N = range(n)
for i in range(n):
    N[i] = z.count(i+1)

ans = 0
for i in range(n):
    ans = ans + N.count(i)/(2**i)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

N, M = list(map(int, input().split()))
node2set_id = defaultdict(int)
set_id2nodes = defaultdict(set)

# idxなどを振る
id_left = [i+1 for i in range(M)]
for i in range(M):
    x, y, z = list(map(int, input().split()))
    #print("from ", set_id2nodes)
    if node2set_id[x] + node2set_id[y] == 0:
        id = id_left.pop()
        # x,yが所属するグループIDを振る
        node2set_id[x] = id
        node2set_id[y] = id

        # グループIDに対するセットを追加
        set_id2nodes[id] |= {x, y}

    elif node2set_id[x] * node2set_id[y] == 0:
        id = node2set_id[x] + node2set_id[y]
        node2set_id[x] = id
        node2set_id[y] = id
        set_id2nodes[id] |= {x, y}
    else:
        if node2set_id[x] - node2set_id[y] == 0:
            continue
        id = node2set_id[x]
        prev_y = y

        # yが所属するグループIDをすべてxのものに置き換える
        for y_idx in set_id2nodes[node2set_id[y]]:
            print(id, y_idx)
            node2set_id[y_idx] = id
            set_id2nodes[id] |= {y_idx}
        #print("x:{},y:{}, prev:{}".format(x, y, prev_y))
        set_id2nodes[prev_y] = {}
    #print("after ", set_id2nodes)
# print([len(m) - 1 for m in set_id2nodes.values()])
num = sum([max(len(m) - 1, 0) for m in set_id2nodes.values()])

print(N-num)

Submission status: Runtime Error

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

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

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if i < j:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

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


###############################################################################


def main():
    n, m = intin()
    xyzlist = intinl(m)

    u = UnionFind(n)
    for x, y, z in xyzlist:
        u.unite(x - 1, y - 1)

    ansset = set()
    for i in range(n):
        ansset.add(u.root(i))

    print(len(ansset))



if __name__ == '__main__':
    main()

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=map(int, input().split())

L=dict()

for i in range(M):
  (x,y,z)=map(int, input().split())
  if x not in L:
    L[x] = [y]
  else:
    L[x].append(y)
  if y not in L:
    L[y] = [x]
  else:
    L[y].append(x)

#print(L)
S=set()
def dfs(a):
  if a in S: return
  S.add(a)
  if a in L: 
    for b in L[a]:
      dfs(b)

cnt = 0
for i in range(1, N+1):
  if i not in S:
    cnt += 1
    dfs(i)
print(cnt)

Submission status: Runtime Error

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

# Union Find
# N = 100
PARENT = list(range(N))

used = set()


def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret


def same(n1, n2):
    return root(n1) == root(n2)


def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2


L = []
for i in range(M):
    x, y, z = [int(x) for x in input().split()]
    x -= 1
    y -= 1

    used.add(x)
    used.add(y)
    rootX = root(x)
    rootY = root(y)

    if z % 2 == 0:
        unite(x, y)

cnt = 0
uf = [root(n) for n in PARENT]

ansset = set(uf) - (set(range(N)) - used)

ans = (len(ansset) + 1) // 2 + (N - len(used))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

N, M = list(map(int, input().split()))
node2set_id = defaultdict(int)
set_id2nodes = defaultdict(set)

# idxなどを振る
id_left = [i+1 for i in range(M)]
for i in range(M):
    x, y, z = list(map(int, input().split()))

    if node2set_id[x] + node2set_id[y] == 0:
        id = id_left.pop()
        # x,yが所属するグループIDを振る
        node2set_id[x] = id
        node2set_id[y] = id

        # グループIDに対するセットを追加
        set_id2nodes[id] |= {x, y}

    elif node2set_id[x] * node2set_id[y] == 0:
        id = node2set_id[x] + node2set_id[y]
        node2set_id[x] = id
        node2set_id[y] = id
        set_id2nodes[id] |= {x, y}
    else:
        if node2set_id[x] - node2set_id[y] == 0:
            continue
        id = node2set_id[x]
        # yが所属するグループIDをすべてxのものに置き換える
        for y_idx in set_id2nodes[node2set_id[y]]:
            node2set_id[y_idx] = id
            set_id2nodes[id] |= {y_idx}
        set_id2nodes[node2set_id[y]] = {}

num = sum([len(m) - 1 for m in set_id2nodes.values()])

print(N-num)

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
    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]:
        solve(i)
        ans += 1

for i in datalist:
    if i == 0:
        ans += 1
        datalist[i] = 1
        solve(i)

print(ans)

Submission status: Runtime Error

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

class UnionFind:
    def __init__(self,N):
        self.root = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.root[a] == a:
            return a
        else:
            self.root[a] = self.root(self.root[a])
            return self.root[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.root[ra] = rb
        else:
            self.root[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(N)
for x,y,z in src:
    x,y = x-1,y-1
    uf.unite(x,y)
print(N - uf.count)

Submission status: Runtime Error

Solution code:
# coding:utf-8

import math
import re

tmp = {}
def recur(x):
    t = tmp[x]
    if t != x:
        return recur(t)
    return x

def main(params):
    n = int(params[0])
    m = int(params[1])
    xyz = params[2:]
    results = {}
    for i in xyz:
        x,y,z = i.split()
        x = int(x)
        y = int(y)
        z = int(z)
        if x in results and y in results:
            if results[x] != results[y]:
                tx = results[x]
                ty = results[y]
                tmp[tx] = ty
        elif x not in results and y in results:
            results[x] = results[y]
            tmp[x] = results[y]
        elif x in results and y not in results:
            results[y] = results[x]
            tmp[y] = results[x]
        elif x not in results and y not in results:
            results[x] = x
            results[y] = x
            tmp[x] = x
            tmp[y] = x
    t = {}
    for i in range(n):
        if i+1 in results:
            key = recur(i+1)
            t[key] = 1
        else:
            t[i+1] = 2
    print len(t)

if __name__ == "__main__":
    n,m = raw_input().split()
    n = int(n)
    m = int(m)
    cnt = m # TODO: edit here
    params = [n,m]
    for i in range(cnt):
        param = raw_input()
        params.append(param)
    main(params)

Submission status: Runtime Error

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

par = [i for i in range(N)]
rank = [0]*N


def root(x):
    tmp = x
    while par[tmp]!=tmp:
        tmp = par[tmp]
    return tmp

def urite(x,y):
    rx = root(x)
    ry = root(y)
    if rx==ry:
        return
    if rank[rx] < rank[ry]:
        rx,ry = ry,rx
    if rank[rx] == rank[ry]:
        rank[rx] += 1
    par[ry] = rx

for xyz in XYZ:
    urite(x,y)

ans = 0
for i in N:
    if par[i] == i:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
//unionfind
typedef pair<int, int> P;
const int MAX_N = 100010;
int m, n;
int par[MAX_N];    //親
int deapth[MAX_N]; //木の深さ
int cnt[MAX_N];
int num;

vector<int> vec[MAX_N];
//n要素で初期化
void init(int n)
{
    for (int i = 0; i < n; i++)
    {
        par[i] = i;
        deapth[i] = 0;
        cnt[i] = 1;
    }
}
//木の根を求める
int find(int x)
{
    if (par[x] == x)
    {
        return x;
    }
    else
    {
        return par[x] = find(par[x]);
    }
}

//xとyの属する集合を併合
void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
        return;
    if (deapth[x] < deapth[y])
    {
        par[x] = y;
        cnt[y] += cnt[x];
    }
    else
    {
        par[y] = x;
        cnt[x] += cnt[y];
        if (deapth[x] == deapth[y])
            deapth[x]++;
    }
}

bool same(int x, int y)
{
    return find(x) == find(y);
}

int main()
{
    cin >> n >> m;
    init(MAX_N);
    vector<P> v;
    for (int i = 0; i < m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        if (z % 2 == 0)
        {
            unite(x, y);
        }
        else
        {
            v.push_back(P(x, y));
            v.push_back(P(y, x));
        }
    }
    for (int i = 0; i < v.size(); i++)
    {
        vec[find(v[i].first)].push_back(find(v[i].second));
    }
    vector<bool> fl(n + 1, false);
    vector<P> u;

    for (int i = 1; i <= n; i++)
    {
        if (fl[find(i)])
            continue;
        fl[find(i)] = true;
        u.push_back(P(cnt[find(i)], find(i)));
    }

    sort(u.begin(), u.end(), greater<P>());

    vector<bool> f(n + 1, false);
    int ans = 0;
    for (int i = 0; i < u.size(); i++)
    {
        if (f[find(u[i].second)])
            continue;
        ans++;
        f[u[i].second] = true;
        for (int i = 0; i < vec[u[i].second].size(); i++)
        {
            int x = vec[u[i].second][i];
            f[find(x)] = true;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!f[find(i)])
            ans++;
    }
    cout << ans << endl;
}

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(belong[num[i][0]]==belong[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(belong,zeros,cluster)
        
print(zeros,cluster)

Submission status: Runtime Error

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

    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

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

for i in range(m):
  x,y,z=map(int,input().split())
  U.union(x-1,y-1)
ans=0
for i,j in enamurate(U.par):
  if i==j:
    ans+=1
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)]

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

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

  roots = set()

  for node in nodes:
    roots.add(node.root)

  print(len(roots))


if __name__ == '__main__':
  main()

Submission status: Runtime Error

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

    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

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

for i in range(m):
  x,y,z=map(int,input().split())
  U.union(x-1,y-1)
ans=0
for i,j in ensmurate(U.par):
  if i==j:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [-1]*n
b = []
for i in range(m):
    x, y, z = map(int, input().split())
    if a[x-1] != -1:
        if a[y-1] != -1:
            if a[x-1] != a[y-1]:
                b[a[x-1]] |= b[a[y-1]]
                for j in b[a[y-1]]:
                    a[j] = a[x-1]
                b.pop(a[y-1])
        else:
            b[a[x-1]].add(y-1)
            a[y-1] = a[x-1]
    else:
        if a[y-1] != -1:
            b[a[y-1]].add(x-1)
            a[x-1] = a[y-1]
        else:
            b.append({x-1, y-1})
            a[x-1] = a[y-1] = len(b) - 1
print(len(b)+a.count(-1))

Submission status: Runtime Error

Solution code:
import numpy as np
N ,M=map(int ,raw_input().split())
D = []
A = []
for i in range(N):
    D.append(())
    A.append(-1)
#print D,A
#print (np.append(D[0],0))
for i in range(M):
    a,b,c=map(int ,raw_input().split())
    x = min(a,b)
    y = max(a,b)
    D[x]=np.append(D[x],int(y))
cost = 0
for i in D:
    d = D[i]
    if len(d)>0:
        if A[i]==-1:
            cost+=1
        A[i] = 0
        for j in d:
            A[j]=0
for i in range(N):
    if A[i]==-1:
        cost+=1
print cost

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = []
for i in range(n):
  b,c,d = map(int,input().split())
  if b in a and c in a:
    m = m-1
  a.append(b)
  a.append(c)
print(n-m)

Submission status: Runtime Error

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

z = x.extend(y)
N = range(n)
for i in range(n):
    N[i] = z.count(i+1)

ans = 0
for i in range(n):
    ans = ans + N.count(i)/(2**i)
print(ans)