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:
#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    std::map<int, int> edge;
    int u, v, w;
    for(int i=0; i < M; i++){
        cin >> u;
        cin >> v;
        cin >> w;
        edge[u] = v;
    }
    int subord = 0;
    for(auto &dic : edge){
        if(edge.count(dic.second)){
            subord ++;
        }
    }
    cout << N - M + subord << endl;
    return 0;


}

Submission status: Runtime Error

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

n, m = map(int, input().split())
xyz = [[] for i in range(n+1)]
for _ in range(m):
    x, y, z = map(int, input().split())
    xyz[x].append(y)
    xyz[y].append(x)
    
ans = 0
visited = [False]*(n+1)
def dfs(x):
    visited[x] = True
    for y in xyz[x]:
        if not visited[y]:
            dfs(y)

for x in range(1, n+1):
    if visited[x]:
        continue
    dfs(x)
    ans += 1
    
# print(visited)
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
xyz = [[] for i in range(n+1)]
for _ in range(m):
    x, y, z = map(int, input().split())
    xyz[x].append(y)
    xyz[y].append(x)
    
ans = 0
visited = [False]*(n+1)
def dfs(x):
    visited[x] = True
    for y in xyz[x]:
        if not visited[y]:
            dfs(y)

for x in range(1, n+1):
    if visited[x]:
        continue
    dfs(x)
    ans += 1
    
# print(visited)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
E = [[] for k in range(N)]

for k in range(M):
    X, Y, Z = map(int,input().split())
    E[X-1].append(Y-1)
    E[Y-1].append(X-1)
G = [-1]*N

def dfs(now,group):
    if G[now] == -1:
        G[now] = group
        for tsugi in E[now]:
            dfs(tsugi,group)

ans = 0
for k in range(N):
    if G[k] == -1:
        dfs(k,ans)
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
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())
	if not same(x,y):
		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:
N=input()

nl=[ [] for i in range(N+1) ]

q=deque()
for i in range(N-1):
	u,v,w=map(int, raw_input().split())
	nl[u].append( (v,w) )
	nl[v].append( (u,w) )

	if i==0:
		Visit[u]=0
		q.append(1)

Visit=[ None for i in range(N+1) ] 


while q:
	x=q.popleft()
	for to,kyori in nl[x]:
		if Visit[to] is None:
			if kyori%2==0:
				Visit[to]=Visit[x]
			else:
				Visit[to]=(Visit[x]+1)%2
			q.append(to)
			

for i in Visit[1:]:
	print i

Submission status: Runtime Error

Solution code:
from collections import deque

N=input()

nl=[ [] for i in range(N+1) ]

q=deque()
for i in range(N-1):
	u,v,w=map(int, raw_input().split())
	nl[u].append( (v,w) )
	nl[v].append( (u,w) )

	if i==0:
		Visit[u]=0
		q.append(1)

Visit=[ None for i in range(N+1) ] 


while q:
	x=q.popleft()
	for to,kyori in nl[x]:
		if Visit[to] is None:
			if kyori%2==0:
				Visit[to]=Visit[x]
			else:
				Visit[to]=(Visit[x]+1)%2
			q.append(to)
			

for i in Visit[1:]:
	print i

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

for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    uni.union(a,b)
t = set([])
for i in range(m):
    p = uni.find(i)
    t.add(p)
print(len(t))

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)
n,m=map(int,input().split())
uni = UnionFind(n-1)

for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    uni.union(a,b)
t = set([])
for i in range(m):
    p = uni.find(i)
    t.add(p)
print(len(t))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]

    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        if self.rx == self.ry:
            return
        self.par[self.rx] = self.ry

    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry

N,M = [int(i) for i in input().split()]
uf = UnionFind(N)

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

ans = set()
for i in range(N):
    ans.add(uf.root(i))
print(len(ans))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]

    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        if self.rx == self.ry:
            return
        self.par[self.rx] = self.ry

    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry

N,M = [int(i) for i in input().split()]
uf = UnionFind(N)

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

ans = set()
for i in range(N):
    ans.add(uf.root(i))
print(uf.par)
print(len(ans))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]
 
    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
 
    def unite(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        if self.rx == self.ry:
            return
        self.par[self.rx] = self.ry
 
    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry
 
N,M = [int(i) for i in input().split()]
uf = UnionFind(N)
 
for _ in range(M):
    x,y,_ = [int(i)-1 for i in input().split()]
    uf.unite(x,y)
 
ans = set()
for i in range(N):
    ans.add(uf.root(i))
 
print(len(ans))

Submission status: Runtime Error

Solution code:
#sys.setrecursionlimit(20000)

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]
 
    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
 
    def unite(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        if self.rx == self.ry:
            return
        self.par[self.rx] = self.ry
 
    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry
 
N,M = [int(i) for i in input().split()]
uf = UnionFind(N)
 
for _ in range(M):
    x,y,_ = [int(i)-1 for i in input().split()]
    uf.unite(x,y)
 
ans = set()
for i in range(N):
    ans.add(uf.root(i))
 
print(len(ans))

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(20000)

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]
 
    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
 
    def unite(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        if self.rx == self.ry:
            return
        self.par[self.rx] = self.ry
 
    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry
 
N,M = [int(i) for i in input().split()]
uf = UnionFind(N)
 
for _ in range(M):
    x,y,_ = [int(i)-1 for i in input().split()]
    uf.unite(x,y)
 
ans = set()
for i in range(N):
    ans.add(uf.root(i))
 
print(len(ans))

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(100000)

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]
 
    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
 
    def unite(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        if self.rx == self.ry:
            return
        self.par[self.rx] = self.ry
 
    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry
 
N,M = [int(i) for i in input().split()]
uf = UnionFind(N)
 
for _ in range(M):
    x,y,_ = [int(i)-1 for i in input().split()]
    uf.unite(x,y)
 
ans = set()
for i in range(N):
    ans.add(uf.root(i))
 
print(len(ans))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3.4

# abc126_e

import sys

sys.setrecursionlimit(10**5)

def main():
    # input
    n, m = [int(s) for s in input().split()]
    to = [list() for _ in range(n)]
    for _ in range(m):
        x, y, _ = [int(s) for s in input().split()]
        x -= 1
        y -= 1
        to[x].append(y)
        to[y].append(x)
    # get ans
    colors = [None] * n
    counter = 0
    def dfs(cur, c):
        if colors[cur] != None:
            return
        colors[cur] = c
        for i in to[cur]:
            dfs(i, c)
    for i in range(n):
        if colors[i] == None:
            dfs(i, counter)
            counter += 1
    ans = counter
    # output
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

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

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

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

cnt = set()
for k, y in pair.items():
    y = root(y)
    cnt.add(y)
print(len(cnt))

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

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

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

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

cnt = set()
for k, y in pair.items():
    ry = root(y)
    cnt.add(ry)
print(len(cnt))

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

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

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

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

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

cnt = set()
for k, y in pair.items():
    ry = root(y)
    cnt.add(ry)
print(len(cnt))

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return True
    else:
        pair[rx] = ry

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

for i in range(1, N+1):
    pair.setdefault(i, i)

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

cnt = set()
for k, y in pair.items():
    ry = root(y)
    cnt.add(ry)
print(len(cnt))

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
 
    def root(self, i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.root(self.parent[i])
            return self.parent[i]
    
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        self.parent[j] = i
N, M = map(int, input().split())
tree = UnionFind(N)
for _ in range(M):
    x, y, z = map(int, input().split())
    tree.union(x-1, y-1)
for i in range(N):
    tree.root(i)
print(len(set(tree.parent)))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
pair = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return True
    else:
        pair[rx] = ry

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

for i in range(1, N+1):
    pair.setdefault(i, i)

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

cnt = set()
for k, y in pair.items():
    ry = root(y)
    cnt.add(ry)
print(len(cnt))

Submission status: Runtime Error

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

    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        if self.rx == self.ry:
            return
        self.par[self.rx] = self.ry

    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry

N,M = [int(i) for i in input().split()]
uf = UnionFind(N)

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

ans = set()
for i in range(N):
    ans.add(uf.root(i))

print(len(ans))

Submission status: Runtime Error

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

class UnionFind():
    def __init__(self, N):
        self.nodes = [i for i in range(N)]

    def root(self, x):
        if self.nodes[x] != x:
            self.nodes[x] = self.root(self.nodes[x])
        return self.nodes[x]

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

    def unite(self, x, y):
        if self.same(x, y):
            return
        self.nodes[self.root(x)] = self.root(y)

uf = UnionFind(N)
anti_list = [[] for _ in range(N)]

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

group = set()
for node in uf.nodes:
    group.add(uf.root(node))

print(len(group))

Submission status: Runtime Error

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    N = int(input())
    color = [-1] * N
    color[0] = 0
    uvw = []
    edge = [[]for _ in range(N)]
    # append=uvw.append
    for i in range(N-1):
        ui, vi, wi = map(int, input().split())
        ui -= 1
        vi -= 1
        edge[ui].append((vi, wi))
        edge[vi].append((ui, wi))
    stack = [0]
    for i in range(N):
        tmp = deque()
        while stack:
            i = stack.pop()
            for e, w in edge[i]:
                if color[e] == -1:
                    stack.append(e)
                    if color[i] == 0:
                        if w % 2 == 0:
                            color[e] = 0
                        else:
                            color[e] = 1
                    else:
                        if w % 2 == 0:
                            color[e] = 1
                        else:
                            color[e] = 0
                # ここを追加--------------------------------------
                # 矛盾判定
                else:
                    if (color[i] == color[e]) != (w % 2 == 0):
                        print(-1)
                        exit()
                # ^^^^^^^^--------------------------------------
        # print(color)
        stack = tmp
    print(*color, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    N = int(input())
    color = [-1] * N
    color[0] = 0
    uvw = []
    edge = [[]for _ in range(N)]
    # append=uvw.append
    for i in range(N-1):
        ui, vi, wi = map(int, input().split())
        ui -= 1
        vi -= 1
        edge[ui].append((vi, wi))
        edge[vi].append((ui, wi))
    stack = [0]
    for i in range(N):
        tmp = deque()
        while stack:
            i = stack.pop()
            for e, w in edge[i]:
                if color[e] == -1:
                    stack.append(e)
                    if color[i] == 0:
                        if w % 2 == 0:
                            color[e] = 0
                        else:
                            color[e] = 1
                    else:
                        if w % 2 == 0:
                            color[e] = 1
                        else:
                            color[e] = 0
                # ここを追加--------------------------------------
                # 矛盾判定
                else:
                    if (color[i] == color[e]) != (x % 2 == 0):
                        print(-1)
                        exit()
                # ^^^^^^^^--------------------------------------
        # print(color)
        stack = tmp
    print(*color, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class UnionFind():
    # 負の値は根で集合の個数
    # 正の値は次の要素を返す
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        self.table[x] = self.find(self.table[x])
        return self.table[x]
        # while self.table[x] >= 0:
        #     #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
        #     x = self.table[x]
        # return x

    # 併合
    def union(self, x, y):
        s1 = self.find(x)  # 代表のIndexを取得する
        s2 = self.find(y)
        if s1 != s2:  # 代表のIndexが違う場合
            if self.table[s1] < self.table[s2]:  # 要素数の多い方へMergeする
                self.table[s2] += self.table[s1]  # 子の和を増やす(-)
                self.table[s1] = s2  # Mergeされる側の代表をする側のインデックスに
            else:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
        return

    def size(self, x):
        # while self.table[x] >= 0:
        #     #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
        #     x = self.table[x]
        return -self.table[self.find(x)]


N, M = [int(n) for n in input().split()]
X = [0]*M
Y = [0]*M
Z = [0]*M
UF = UnionFind(N)
adj = [[0, []] for _ in range(N)]
for i in range(M):
    X[i], Y[i], Z[i] = [int(n) for n in input().split()]
    Z[i] %= 2
    X[i] -= 1
    Y[i] -= 1
    UF.union(X[i], Y[i])
s = set([UF.find(0)])
ans = 1

for i in range(1, N):
    tmp = UF.find(i)
    if not(tmp in s):
        ans += 1
        s.add(tmp)
print(ans)

Submission status: Runtime Error

Solution code:
# coding:utf-8

import math
import re

tmp = {}
def recur(x):
    if x in tmp:
        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[y] = tx
        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:
# coding:utf-8

import math
import re

tmp = {}
def recur(x):
    if x in tmp:
        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:
def union_find():
    # グラフの連結していないグループの数をunion_findで求める
    def get_parent(node):
        if par[node] == -1:
            return node
        else:
            par[node] = get_parent(par[node])
            return par[node]

    def merge(i, j):
        i = get_parent(i)
        j = get_parent(j)
        if i != j:
            par[j] = i
        return

    n, m = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(m)]
    par = [-1] * n
    for x, y in xy:
        merge(x-1, y-1)
    print(par.count(-1))


union_find()

Submission status: Runtime Error

Solution code:
'''input
100000 1
1 100000 100
'''

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

vien = [[] for _ in range(N)]

for _ in range(M):
	a, b, w = [int(x) for x in input().split()]
	a -= 1
	b -= 1
	w = w & 1
	vien[a].append(b)
	vien[b].append(a)

been = [False]*N
ats = 0
def dfs(x):
	been[x] = True
	for u in vien[x]:
		if not been[u]:
			dfs(u)


for i in range(N):
	if been[i]: continue

	ats += 1
	dfs(i)

print(ats)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
num_edges = M
edges = [list(map(int, input().split())) for i in range(num_edges)]
adj = [[] for i in range(N+1)]
for ed in edges:
    adj[ed[0]] += [[ed[1], ed[2]]]
    adj[ed[1]] += [[ed[0], ed[2]]]
col_list = [-1 for i in range(N+1)]

def recfun(v, col):
    col_list[v] = col #色を更新
    for ed in adj[v]: #隣接する頂点をみる
        if col_list[ed[0]] == -1: #更新していない場合
            recfun(ed[0], col) #同じ色でその先をみる
count = 0
for i in range(1, N+1):
    if col_list[i] == -1:
        count +=1
        recfun(i, count)
print(count)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**5)

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

counter = 0
c = [-1 for i in range(n)]
p = [[] for n in range(n)]

for i in range(m):
    x, y, z = list(map(int, input().split()))
    x -= 1
    y -= 1
    p[x].append(y)
    p[y].append(x)

def dfs(num, depth):
    if c[num] != -1:
        return
    else:
        c[num] = depth
    for i in p[num]:
        dfs(i, depth)

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

print(max(c))

Submission status: Runtime Error

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

counter = 0
c = [-1 for i in range(n)]
p = [[] for n in range(n)]

for i in range(m):
    x, y, z = list(map(int, input().split()))
    x -= 1
    y -= 1
    p[x].append(y)
    p[y].append(x)

def dfs(num, depth):
    if c[num] != -1:
        return
    else:
        c[num] = depth
    for i in p[num]:
        dfs(i, depth)

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

print(max(c))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
import sys
s = sys.stdin.readlines()
N, M = map(int, s[0].split())
look_set_list = []
num_of_uniq_num = 0
for e in s[1:]:
    X, Y, Z = map(int, e.split())
    x_index = -1
    y_index = -1
    for i, ls in enumerate(look_set_list):
        if X in ls:
            x_index = i
        if Y in ls:
            y_index = i
    if x_index == -1:
        num_of_uniq_num += 1
        if y_index == -1:
            num_of_uniq_num += 1
            look_set_list.append(set([X, Y]))
        else:
            look_set_list[y_index].add(X)
    else:
        if y_index == -1:
            num_of_uniq_num += 1
            look_set_list[y_index].add(Y)
        else:
            if x_index == y_index:
                continue
            else:
                y_set = look_set_list.pop(y_index)
                look_set_list[x_index] = look_set_list[x_index].union(y_set)

O = N - num_of_uniq_num + len(look_set_list)
print(O)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
import sys
s = sys.stdin.readlines()
N, M = map(int, s[0].split())
look_set_list = []
num_of_uniq_num = 0
for e in s[1:]:
    X, Y, Z = map(int, e.split())
    x_index = -1
    y_index = -1
    for i, ls in enumerate(look_set_list):
        if X in ls:
            x_index = i
        if Y in ls:
            y_index = i
    if x_index == -1:
        num_of_uniq_num += 1
        if y_index == -1:
            num_of_uniq_num += 1
            look_set_list.append(set([X, Y]))
        else:
            look_set_list[y_index].add(X)
    else:
        if y_index == -1:
            num_of_uniq_num += 1
            look_set_list[y_index].add(Y)
        else:
            if x_index == y_index:
                continue
            else:
                y_set = look_set_list.pop(y_index)
                look_set_list[x_index] = look_set_list[x_index].union(y_set)

O = N - num_of_uniq_num + len(look_set_list)
print(O)
print(num_of_uniq_num)
print(look_set_list)

Submission status: Runtime Error

Solution code:
# unionfind

class UnionFind(object):

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

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

    def unite(self, xx, yy):
        xp = self.find_parent(xx)
        yp = self.find_parent(yy)
        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:
# unionfind

class UnionFind(object):

    def __init__(self, n):
        self.n = n
        self.parent = list(range(self.n))
        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))