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:
class UnionFind:
    def __init__(self, num):
        self.p = [x for x in range(num)]
    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.p[ry] = rx

def main():
    N, M = (int(x) for x in input().split())
    u = UnionFind(N)

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

    rlist = set()
    for i in range(N):
        rlist.add(u.root(i))

    print(len(rlist))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, num):
        self.p = [x for x in range(num)]
    def root(self, x):
        if self.p[x] == x:
            return x
        self.p[x] = self.root(self.p[x])
        return self.p[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        self.p[rx] = ry

def main():
    N, M = (int(x) for x in input().split())
    u = UnionFind(N)

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

    rlist = set()
    for i in range(N):
        parent = u.root(i)
        rlist.add(parent)

    print(len(rlist))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, num):
        self.p = [x for x in range(num+1)]
    def root(self, x):
        if self.p[x] == x:
            return x
        self.p[x] = self.root(self.p[x])
        return self.p[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx is ry:
            return
        self.p[rx] = ry

def main():
    N, M = (int(x) for x in input().split())
    u = UnionFind(N)

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

    rlist = set([])
    for i in range(N):
        parent = u.root(i)
        rlist.add(parent)

    print(len(rlist))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, num):
        self.p = [x for x in range(num)]
    def root(self, x):
        if self.p[x] == x:
            return x
        self.p[x] = self.root(self.p[x])
        return self.p[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx is ry:
            return
        self.p[rx] = ry

def main():
    N, M = (int(x) for x in input().split())
    u = UnionFind(N)

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

    rlist = set([])
    for i in range(N):
        parent = u.root(i)
        rlist.add(parent)

    print(len(rlist))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, num):
        self.p = [x for x in range(num)]
    def root(self, x):
        if self.p[x] == x:
            return x
        self.p[x] = self.p[self.p[x]]
        return self.root(self.p[x])
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx is ry:
            return
        self.p[rx] = ry
    def same(self, x, y):
        return self.root(x) == self.root(y)

def main():
    N, M = (int(x) for x in input().split())
    u = UnionFind(N)

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

    rlist = set([])
    for i in range(N):
        parent = u.root(i)
        rlist.add(parent)

    print(len(rlist))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, num):
        self.p = [x for x in range(num)]
    def root(self, x):
        if self.p[x] == x:
            return x
        self.p[x] = self.root(self.p[x])
        return self.p[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx is ry:
            return
        self.p[rx] = ry
    def same(self, x, y):
        return self.root(x) == self.root(y)

def main():
    N, M = (int(x) for x in input().split())
    u = UnionFind(N)

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

    rlist = set([])
    for i in range(N):
        parent = u.root(i)
        rlist.add(parent)

    print(len(rlist))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, NUM):
        self.p = [x for x in range(NUM)]
    def root(self, x):
        if self.p[x] == x:
            return x
        self.p[x] = self.root(self.p[x])
        return self.p[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx is ry:
            return
        self.p[rx] = ry
    def same(self, x, y):
        return self.root(x) == self.root(y)

def main():
    N, M = (int(x) for x in input().split())
    u = UnionFind(N)

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

    rlist = set([])
    for i in range(N):
        parent = u.root(i)
        rlist.add(parent)

    print(len(rlist))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

def root(table, i):
    if table[i] == i:
        return i
    table[i] = root(table, table[i])
    return table[i]


def union(table, a, b):
    root1 = root(table, min(a, b))
    root2 = root(table, max(a, b))
    if root1 != root2:
        table[root1] = root2


table = {}
n, m = map(int, input().split())
for _ in range(m):
    x, y, z = map(int, input().split())
    if x not in table:
        table[x] = x
    if y not in table:
        table[y] = y
    union(table, x, y)

s = set()
for i in range(1, n + 1):
    if i in table:
        s.add(root(table, i))
    else:
        s.add(i)

print(len(s))

Submission status: Runtime Error

Solution code:

def root(table, i):
    if table[i] == i:
        return i
    table[i] = root(table, table[i])
    return table[i]


def union(table, a, b):
    table[root(table, min(a, b))] = root(table, max(a, b))


table = {}
n, m = map(int, input().split())
for _ in range(m):
    x, y, z = map(int, input().split())
    if x not in table:
        table[x] = x
    if y not in table:
        table[y] = y
    union(table, x, y)

s = set()
for i in range(1, n + 1):
    if i in table:
        s.add(root(table, i))
    else:
        s.add(i)

print(len(s))

Submission status: Runtime Error

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

xyz = [list(map(int, input().split())) for _ in range(M)]

# 魔法実行回数
magic_act_num = 0

known = [False for x in range(N)]
judge = 0
index = 0
for x, y, _ in xyz:
    x = x-1
    y = y-1
    if known[x] and known[y]:
        continue;

    # zは気にしなくてよい
    if known[x]:
        if known[y] is False:
            known[y] = True
            judge += 1
    else:
        if known[y]:
            known[x] = True
            judge += 1
        else:
            known[x] = True
            known[y] = True
            judge += 2
            magic_act_num += 1
    i = 0
    for a, b, _ in xyz:
        if i <= index:
            continue
        a = a - 1;
        b = b - 1;
        if known[a] is x and known[b] is y:
            continue
        if known[a] is y and known[b] is x:
            continue
        if known[a] is x:
            if known[b] is not y:
                known[b] = True
        if known[a] is y:
            if known[b] is not x:
                known[b] = True
        if known[b] is x:
            if known[a] is not y:
                known[a] = True
        if known[b] is y:
            if known[a] is not x:
                known[a] = True
        i++
    index++

magic_act_num += (N-judge)

print(magic_act_num)

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.find(self.par[x])
    def same_chk(self,x,y):#x,yが同じグループに所属するか確認
        return self.find(x)==self.find(y)
    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())
xyz=[]
for i in range(n-1):
    xyz.append(list(map(int, input().split())))
#n,m=6,5
#xyz=[[1,2,1],[2,3,2],[1,3,3],[4,5,4],[5,6,5]]
uf=UnionFind(n)
for i in range(m):
    uf.union(xyz[i][0],xyz[i][1])
root=[]
for i in range(1,n+1):
    temp_root0=uf.find(i)
    if temp_root0 not in root:
        root.append(temp_root0)
    temp_root1=uf.find(i)
    if temp_root1 not in root:
        root.append(temp_root1)
print(len(root))

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
xyz=[]
for i in range(n-1):
    xyz.append(list(map(int, input().split())))
#n,m=6,5
#xyz=[[1,2,1],[2,3,2],[1,3,3],[4,5,4],[5,6,5]]
uf=UnionFind(n)
for i in range(m):
    uf.union(xyz[i][0],xyz[i][1])
root=[]
for i in range(1,n+1):
    temp_root0=uf.find(i)
    if temp_root0 not in root:
        root.append(temp_root0)
    temp_root1=uf.find(i)
    if temp_root1 not in root:
        root.append(temp_root1)
print(len(root),root)

Submission status: Runtime Error

Solution code:
#UnionFindクラス
class UnionFind(object):
 
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        self.size=[1 for i in range(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 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 same(self, x, y):
        return self.find(x) == self.find(y)
    
    def tree_size(self,x):
        return self.size[self.find(x)]
    
def main():
    n,m = map(int, input().split())
    uf = UnionFind(n)
    for i in range(m):
        x,y,z = map(int, input().split())
        uf.union(x,y)
    res = n
    for i in range(n):
        if uf.par[i] == i:
            res -= 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

adj={i: set() for i in range(1,N+1)}
for i in range(M):
  x,y,z=map(int, input().split())
  adj[x].add(y)
  adj[y].add(x)
V=set()
def dfs(v):
  if v not in V:
    V.add(v)
    for u in adj[v]: dfs(u)
cnt=0
for i in range(1,N+1):
  if i not in V:
    cnt += 1
    dfs(i)
print(cnt)

Submission status: Runtime Error

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

adj=[set() for i in range(N)]
for i in range(M):
  x,y,z=map(int, input().split())
  adj[x-1].add(y-1)
  adj[y-1].add(x-1)
V=set()
def dfs(v):
  if v not in V:
    V.add(v)
    for u in adj[v]: dfs(u)
cnt=0
for i in range(N):
  if i not in V:
    cnt += 1
    dfs(i)
print(cnt)

Submission status: Runtime Error

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

adj=dict()
for i in range(M):
  x,y,z=map(int, input().split())
  if x in adj: adj[x].add(y)
  else: adj[x]={y}
  if y in adj: adj[y].add(x)
  else: adj[y]={x}
#print(outgoing)
#print(incoming)
V=set()
def dfs(v):
  if v not in V:
    V.add(v)
    if v in adj:
      for u in adj[v]: dfs(u)
cnt=0
for i in range(1, N+1):
  if i not in V:
    cnt += 1
    dfs(i)
print(cnt)

Submission status: Runtime Error

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

outgoing=dict()
incoming=dict()
for i in range(M):
  x,y,z=map(int, input().split())
  if x in outgoing: outgoing[x].add(y)
  else: outgoing[x]={y}
  if y in incoming: incoming[y].add(x)
  else: incoming[y]={x}
#print(outgoing)
#print(incoming)
V=set()
def dfs(v):
  if v not in V:
    V.add(v)
    if v in outgoing:
      for u in outgoing[v]: dfs(u)
    if v in incoming:
      for u in incoming[v]: dfs(u)
cnt=0
for i in range(1, N+1):
  if i not in V:
    cnt += 1
    dfs(i)
print(cnt)

Submission status: Runtime Error

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

outgoing=dict()
incoming=dict()
for i in range(M):
  x,y,z=map(int, input().split())
  if x in outgoing: outgoing[x].add(y)
  else: outgoing[x]={y}
  if y in incoming: incoming[y].add(x)
  else: incoming[y]={x}
#print(outgoing)
#print(incoming)

V=set()
def dfs(v):
  if v not in V:
    V.add(v)
    og=set() if v not in outgoing else outgoing[v]
    ic=set() if v not in incoming else incoming[v]
    for u in og.union(ic):
      dfs(u)

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

Submission status: Runtime Error

Solution code:
# Undirected Graph
class Graph:

    def __init__(self, num_of_vertexes):
        self.v = num_of_vertexes
        self.e = [[] for i in range(num_of_vertexes)]

    def dfs(self, tmp, v, visited):
        visited[v] = True
        tmp.append(v)
        for i in self.e[v]:
            if visited[i] == False:
                tmp = self.dfs(tmp, i, visited)
        return tmp

    def addEdge(self, v, w):
        self.e[v].append(w)
        self.e[w].append(v)

    def connComponents(self):
        ret = []
        visited = []
        for i in range(self.v):
            visited.append(False)
        for v in range(self.v):
            if visited[v] == False:
                tmp = []
                ret.append(self.dfs(tmp, v, visited))
        return ret

# main
N, M = (int(x) for x in input().split())
l = [[None]*3 for i in range(M)]
for i in range(M):
    index = 0
    for x in input().split():
        l[i][index] = int(x)
        index += 1

X = [l[i][0] for i in range(M)]
Y = [l[i][1] for i in range(M)]

g = Graph(N)
for i in range(M):
    g.addEdge(X[i]-1, Y[i]-1)

print(len(g.connComponents()))

Submission status: Runtime Error

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

li=list(range(1,n+1))

for i in range(m):
    x, y, z=map(int, input().split())
    if z%2==0:
        li[max(x,y)-1]=li[min(x,y)-1]
    else:
        li[max(x,y)-1]=-li[min(x,y)-1]
    print(li)

for i in range(n):
    if li[i]!=i+1:
        li[i]=0

li2=[0]*(n+1)

for i in range(n):
    li2[i]=li[i]/(i+1)

print(sum(li2)//1)

Submission status: Runtime Error

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

li=list(range(1,n+1))

for i in range(m):
    x, y, z=map(int, input().split())
    if z%2==0:
        li[max(x,y)-1]=li[min(x,y)-1]
    else:
        li[max(x,y)-1]=-li[min(x,y)-1]
    print(li)

for i in range(n):
    if li[i]!=i+1:
        li[i]=0

li2=[0]*(n+1)

for i in range(n):
    li2[i]=li[i]/(i+1)

print(sum(li2))

Submission status: Runtime Error

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

li=list(range(1,n+1))

for i in range(m):
    x, y, z=map(int, input().split())
    if z%2==0:
        li[max(x,y)-1]=li[min(x,y)-1]
    else:
        li[max(x,y)-1]=-li[min(x,y)-1]

for i in range(n):
    if li[i]<0:
        li[i]*=-1

li2=[0]*n

for i in range(n):
    li2[li[i]]=1

print(sum(li2))

Submission status: Runtime Error

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

#魔法実行回数
magic_act_num = 0

known = [False for x in range(N)]
judge = 0
for i in range(M):
	x,y,z = (int(x) for x in input().split())

	# zは気にしなくてよい
	if i == 0:
		known[x-1]=True
		known[y-1]=True
		judge += 2
		magic_act_num+=1
	else:
		if known[x-1] == True:
			if known[y-1] == True:
				continue
			else:
				known[y-1] = True
				judge += 1
		else:
			if known[y] == True:
				known[x-1] = True
				judge += 1
			else:
				known[x-1] = True
				known[y-1] = True
				judge += 2
				magic_act_num+=1

magic_act_num += (N-judge)

print(magic_act_num)

Submission status: Runtime Error

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

#魔法実行回数
magic_act_num = 0

known = [False for x in range(N)]
judge = 0
for i in range(M):
	x,y,z = (int(x) for x in input().split())

	# zは気にしなくてよい
	if i == 0:
		known[x]=True
		known[y]=True
		judge += 2
		magic_act_num+=1
	else:
		if known[x] == True:
			if known[y] == True:
				continue
			else:
				known[y] = True
				judge += 1
		else:
			if known[y] == True:
				known[x] = True
				judge += 1
			else:
				known[x] = True
				known[y] = True
				judge += 2
				magic_act_num+=1

magic_act_num += (N-judge)

print(magic_act_num)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>

using namespace std;

class unionFind{
    int nodeSize;
    vector<int> parent;

public:
    unionFind(int n):nodeSize(n){
        parent = vector<int>(n+1,-1);
    }

    int getRoot(int a){
        if(parent[a] < 0){
            return a;
        }
        return parent[a] = getRoot(a);
    }

    bool isSameParent(int a,int b){
        return getRoot(a) == getRoot(b);
    }

    bool isRoot(int a){
        if(parent[a] < 0){
            return true;
        }
        return false;
    }

    void unite(int a,int b){
        if(isSameParent(a,b)){
            return;
        }
        int aParent = getRoot(a);
        int bParent = getRoot(b);

        if(abs(parent[aParent]) > abs(parent[bParent])){
            parent[aParent] += parent[bParent];
            parent[bParent] = aParent;
        }else{
            parent[bParent] += parent[bParent];
            parent[aParent] = bParent;
        }
    }
};

int main(){
    int n,m;
    cin >> n >> m;

    vector<int> x(m),y(m),z(m);
    for(int i = 0; i < m; i++){
        cin >> x[i] >> y[i] >> z[i];
    }

    unionFind uf(n);

    for(int i = 0; i < m; i++){
        uf.unite(x[i],y[i]);
    }

    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(uf.isRoot(i)){
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

Submission status: Runtime Error

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

N,M = map(int,input().split())
tree = [[] for i in range(N)]
for i in range(M):
    X,Y,Z = map(int,input().split())
    X -= 1
    Y -= 1
    tree[X] += [Y]
    tree[Y] += [X]

# print(tree)
used = [0 for i in range(N)]

def dfs(node,p):
    used[node] = 1
    # print(tree[node])
    for new in tree[node]:
        if new == p or used[new] == 1:continue
        dfs(new,node)

cnt = 0
while sum(used) < len(used):
    for i in range(N):
        if used[i] == 0:
            dfs(i,-1)
            cnt += 1

ans = N - (sum(used) - cnt)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
c = [-1 for _ in range(N)]
connect = [[] for _ in range(N)]

for i in range(M):
    X, Y, Z = map(int,input().split())
    X -= 1
    Y -= 1
    connect[X].append(Y)
    connect[Y].append(X)
    
def dfs(num, depth):
    if c[num] == -1:
      c[num] = depth
      for i in connect[num]:
        dfs(i,depth)
    
count = 0

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

print(max(c))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
g = defaultdict(list)

N, M = map(int, input().split())
for i in range(M):
    X, Y, Z = map(int, input().split())
    g[X].append(Y)
    g[Y].append(X)

ans = 0
not_visited = {i:True for i in range(1, N+1)}

def dfs(v):
    if v in not_visited:
        del not_visited[v]
    for c in g[v]:
        if c in not_visited:
            dfs(c)

s = 1
while True:
    dfs(s)
    ans += 1
    if not len(not_visited):
        break
    for v in not_visited.keys():
        s = v
        break

print(ans)

Submission status: Runtime Error

Solution code:
def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par = get_par(par_list[x])
    par_list[x] = par
    return par

N,M=map(int,input().split())
par_list = [i for i in range(N+1)]
for i in range(M):
  Xi,Yi,Zi=map(int,input().split())
  par_Xi = get_par(Xi)
  par_Yi = get_par(Yi)
  if par_Xi != par_Yi:
    par_list[par_Yi] = par_Xi
    
#print(par_list)
set_uf = set()
for par in par_list[1:]:
  set_uf.add(get_par(par))
  
print(len(set_uf))

Submission status: Runtime Error

Solution code:
def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par = get_par(par_list[x])
    par_list[x] = par
    return par

N,M=map(int,input().split())
par_list = [i for i in range(N+1)]
for i in range(M):
  Xi,Yi,Zi=map(int,input().split())
  par_Xi = get_par(Xi)
  par_Yi = get_par(Yi)
  if par_Xi != par_Yi:
    par_list[par_Yi] = par_list[par_Xi]
    
#print(par_list)
set_uf = set()
for par in par_list[1:]:
  set_uf.add(get_par(par))
  
print(len(set_uf))

Submission status: Runtime Error

Solution code:
def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par = get_par(par_list[x])
    par_list[x] = par
    return par

N,M=map(int,input().split())
par_list = [i for i in range(N)]
for i in range(M):
  Xi,Yi,Zi=map(int,input().split())
  par_Xi = get_par(Xi-1)
  par_Yi = get_par(Yi-1)
  if par_Xi != par_Yi:
    par_list[par_Yi] = par_list[par_Xi]
    
#print(par_list)
set_uf = set()
for par in par_list:
  set_uf.add(get_par(par))
  
print(len(set_uf))

Submission status: Runtime Error

Solution code:
import collections

def root(X):
	if cards[X]==X:
		return X
	else:
		cards[X]=root(cards[X])
		return cards[X]
def unite(X,Y):
	x=root(X)
	y=root(Y)
	if x==y:
		return
	else:
		cards[x]=y
def same(X,Y):
	return root(X)==root(Y)
def show(x):
	print(cards[x])
		
N,M=[int(i) for i in input().split()]
cards=[i for i in range(N+1)]
for i in range(M):
	X,Y,Z=[int(i) for i in input().split()]
	if same(X,Y):
		pass
	else:
		unite(X,Y)
a=[]
for i in range(1,N+1):
	a.append(root(cards[i]))
print(len(set(a)))

Submission status: Runtime Error

Solution code:

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

G = {}
V = []

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

# G = {1: [2], 2: [1]}
# N = 3
# G = {1: [2, 3], 2: [1, 3], 3: [2, 1], 4: [5], 5: [4, 6], 6: [5]}
# N = len(G)
# G = {1: [100000], 100000: [1]}
# N = 100000

def visit(visited, current):
    for v in G[current]:
        if v not in visited:
            visited.append(v)
            visit(visited, v)
    return visited

# print(G)

# print(visit([1], 1))
# print(visit([6], 6))

n = len(G)
k = 0
while len(G) > 0:
    x = next(iter(G))
    for y in visit([x], x):
        del G[y]
    k += 1

print(k+N-n)

Submission status: Runtime Error

Solution code:

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

G = {}
V = []

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

# G = {1: [2], 2: [1]}
# N = 3
# G = {1: [2, 3], 2: [1, 3], 3: [2, 1], 4: [5], 5: [4, 6], 6: [5]}
# N = len(G)
# G = {1: [100000], 100000: [1]}
# N = 100000

def visit(visited, current):
    for v in G[current]:
        if v not in visited:
            visited.append(v)
            visit(visited, v)
    return visited

# print(G)

# print(visit([1], 1))
# print(visit([6], 6))

V = set(G.keys())
n = len(V)
k = 0
while len(V) > 0:
    x = list(V)[0]
    V = V - set(visit([x], x))
    k += 1

print(k+N-n)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        self.total = 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 same_check(self, x, y):
        return self.find[x] == self.find[y]
    def unite(self, x, y):
        if self.same_check(x, y):
            return
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.total -= 1
        else:
            self.par[y] = x
            self.total -= 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
n,m = map(int, input().split())
union = UnionFind(n)
for i in range(m):
    x,y,z = map(int, input().split())
    union.unite(x-1, y-1)
print(union.total)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, N):
        # par[a]=b : b is parent of a
        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):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry: self.par[rx] = ry

    def same(self, x, y):
        return self.root(x) == self.root(y)
            
N, M = list(map(int, input().split()))
uf = UnionFind(N)

edges = [list(map(int, input().split())) for i in range(M)]
for u, v, w in edges:
    uf.unite(u-1, v-1)

for i in range(N):
    uf.root(i)

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

Submission status: Runtime Error

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

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

def find(x):
  if par[x] == x:
    return x
  return find(par[x])

def unite(x,y):
  root_x = find(x)
  root_y = find(y)
  if rank[root_x] > rank[root_y]:
    par[root_y] = root_x
  elif rank[x] > rank[y]:
    par[root_x] = root_y
  else:
    par[root_y] = root_x
    rank[root_x] += 1


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

roo = []

for i in range(n):
  roo.append(find(i+1))

print(len(set(roo)))

Submission status: Runtime Error

Solution code:
def root(x):
    if c[x] == x:
        return x
    else:
        c[x] = root(c[x])
        return c[x]


def uni(x,y):
    rx = root(x)
    ry = root(y)
    c[ry] = rx


n, m = map(int, input().split())
c = [i for i in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    uni(x,y)

for i in range(n):
    root(i)

print(len(set(c)))

Submission status: Runtime Error

Solution code:
def get_par(x):
  if x == par_list[x]:
    return x
  else:
    return get_par(par_list[x])

N,M=map(int,input().split())
par_list = [i for i in range(N)]
for i in range(M):
  Xi,Yi,Zi=map(int,input().split())
  par_Xi = get_par(Xi-1)
  par_Yi = get_par(Yi-1)
  if par_Xi != par_Yi:
    par_list[par_Yi] = par_list[par_Xi]
    
set_uf = set()
for par in par_list:
  set_uf.add(par)
  
print(len(set_uf))

Submission status: Runtime Error

Solution code:
from collections import deque

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

xy = {i:[] for i in range(1,N+1)}
visited = {i:False for i in range(1,N+1)}

for _ in range(M):
  x,y,z = map(int,input().split())
  xy[x].append(y)
  xy[y].append(x)

def dfs(p):
  visited[p] = True
  for q in xy[p]:
    if visited[q]:
      pass
    else:
      dfs(q)
      
count = 0
for i in range(1,N+1):
  if visited[i]:
    continue
  else:
    count += 1
    dfs(i)
print(count)

Submission status: Runtime Error

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

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

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

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


N, M = map(int, input().split())
rf = UniteFind(N)

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

m = {i: -1 for i in range(N)}
ans = 0

for i in range(N):
    if m[rf.root(i)] == -1:
        m[rf.root(i)] = 1
        ans += 1

print(ans)

Submission status: Runtime Error

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

p = list(range(n))


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


def union(x, y):
    x, y = find(x), find(y)
    p[y] = x


for _ in range(m):
    x, y, z = [int(i) - 1 for i in input().split()]
    if find(x) != find(y):
        union(x, y)

ans = set()
for i in range(n):
    find(i)
print(len(set(p)))

Submission status: Runtime Error

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

p = list(range(n))


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


def union(x, y):
    x, y = find(x), find(y)
    p[y] = x


for i in range(m):
    x, y, z = [int(i) - 1 for i in input().split()]
    if find(x) != find(y):
        union(x, y)

ans = set()
for i in range(n):
    find(i)
print(len(set(p)))

Submission status: Runtime Error

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

p = list(range(n))


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


def union(x, y):
    x, y = find(x), find(y)
    p[y] = x


for i in range(m):
    x, y, z = [int(i) - 1 for i in input().split()]
    if find(x) != find(y):
        union(x, y)

ans = set()
for i in list(set(list(p))):
    ans.add(find(i))
print(len(ans))

Submission status: Runtime Error

Solution code:
from collections import deque
n = int(input())
q = deque(maxlen=n-1)

for i in range(n - 1):
    a, b, c = map(int, input().split())
    q.append([a-1, b-1, c % 2])

cllist = [-1] * n
a, b, c = q.popleft()
cllist[a] = 0
cllist[b] = c
while q:
    a, b, c = q.popleft()
    if cllist[a] != -1:
        cllist[b] = (cllist[a] + c) % 2
    elif cllist[b] != -1:
        cllist[a] = (cllist[b] + c) % 2
    else:
        q.append([a, b, c])
print(*cllist)