Problem:
 Score : 700 points    Problem Statement Snuke's mother gave Snuke an undirected graph consisting of N vertices numbered 0 to N-1 and M edges.
This graph was connected and contained no parallel edges or self-loops.  One day, Snuke broke this graph.
Fortunately, he remembered Q clues about the graph.
The i -th clue ( 0 \leq i \leq Q-1 ) is represented as integers A_i,B_i,C_i and means the following:   If C_i=0 : there was exactly one simple path (a path that never visits the same vertex twice) from Vertex A_i to B_i .  If C_i=1 : there were two or more simple paths from Vertex A_i to B_i .   Snuke is not sure if his memory is correct, and worried whether there is a graph that matches these Q clues.
Determine if there exists a graph that matches Snuke's memory.      Constraints  2 \leq N \leq 10^5  N-1 \leq M \leq N \times (N-1)/2  1 \leq Q \leq 10^5  0 \leq A_i,B_i \leq N-1  A_i \neq B_i  0 \leq C_i \leq 1  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  M  Q  A_0  B_0  C_0  A_1  B_1  C_1  \vdots  A_{Q-1}  B_{Q-1}  C_{Q-1}       Output If there exists a graph that matches Snuke's memory, print Yes ; otherwise, print No .        Sample Input 1 5 5 3
0 1 0
1 2 1
2 3 0      Sample Output 1 Yes  For example, consider a graph with edges (0,1),(1,2),(1,4),(2,3),(2,4) . This graph matches the clues.       Sample Input 2 4 4 3
0 1 0
1 2 1
2 3 0      Sample Output 2 No       Sample Input 3 10 9 9
7 6 0
4 5 1
9 7 0
2 9 0
2 3 0
4 1 0
8 0 0
9 1 0
3 0 0      Sample Output 3 No

Solution (Python):
import sys
input=sys.stdin.readline

def find_parent(x):
    y=parent[x]
    if y<0:
        return x
    parent[x]=find_parent(y)
    return parent[x]

def connect(a,b):
    c=find_parent(a)
    d=find_parent(b)
    if c==d:
        return
    if parent[c]<parent[d]:
        parent[c]+=parent[d]
        parent[d]=c
    else:
        parent[d]+=parent[c]
        parent[c]=d
    return

N,M,Q=map(int,input().split())
data=[[],[]]
for i in range(Q):
    a,b,c=map(int,input().split())
    data[c].append((a,b))
    
parent=[-1]*N
for a,b in data[0]:
    connect(a,b)

cnt=0
for u in parent:
    if u<0:
        cnt+=1

for a,b in data[1]:
    if find_parent(a)==find_parent(b):
        print("No")
        sys.exit()

if M==N-1:
    if not data[1]:
        print("Yes")
    else:
        print("No")
else:
    M-=N
    if M<=cnt*(cnt-1)//2-cnt:
        print("Yes")
    else:
        print("No")

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

N,M,Q = map(int,readline().split())
ABC = np.array(read().split(),np.int64)

A = ABC[::3]
B = ABC[1::3]
C = ABC[2::3]

zero = (C == 0)
A0 = A[zero]; B0 = B[zero]

graph = csr_matrix((np.ones(len(A0)),(A0,B0)),(N,N))
Ncomp,comp = connected_components(graph)

A1 = A[~zero]; B1 = B[~zero]

if (comp[A1] == comp[B1]).any():
    print('No')
    exit()

lower = N if len(A1) >= 1 else N - 1
upper = Ncomp * (Ncomp-1) // 2 + (N - Ncomp)

if lower <= M <= upper:
    print('Yes')
else:
    print('No')

Solution (Python):
import sys

input = sys.stdin.readline

N, M, Q = map(int, input().split())
E = [list(map(int, input().split())) for i in range(Q)]
f = [i for i in range(N)]
def find(x):
    if x != f[x]:
        f[x] = find(f[x])
    return f[x]
def union(x, y):
    fx, fy = find(x), find(y)
    if fx == fy:    return False
    f[fx] = fy
    return True
   
E1 = []
for a, b, c in E:
    if c == 0:
        union(a, b)
    else:
        E1.append((a, b))

par = [find(x) for x in range(N)]
for a, b in E1:
    if par[a] == par[b]:
        print('No')
        exit()
C = len(set(par))

if len(E1) == 0:
    if N - 1 <= M <= (N - C) + C * (C - 1) // 2:
        print("Yes")
    else:
        print("No")

else:
    if N <= M <= (N - C) + C * (C - 1) // 2:
        print("Yes")
    else:
        print("No")

Solution (Python):
s = input().split(" ")
n = int(s[0])
m = int(s[1])
q = int(s[2])
path_list =[]
rank = [0 for i in range(n)]
multi = []

for i in range(q):
    sp = input().split(" ")
    path = [int(pstr) for pstr in sp]
    path_list.append(path)

par = [i for i in range(n)]





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


def unite(x,y):
    rx = root_find(x)
    ry = root_find(y)

    if rx != ry:
        if rank[x] > rank[y]:
            par[y] = rx
        elif rank[x] == rank[y]:
            par[y] = rx
            rank[x] += 1
        else:
            par[x] = ry


for i in range(q):
    a = path_list[i][0]
    b = path_list[i][1]
    c = path_list[i][2]
    
    if c == 0 :
        pa = root_find(a)
        pb = root_find(b)
        if pa != pb:
            unite(pa,pb)
    else:
        multi.append((a,b))
        

"""
だめなじょうけん
・a,bが木であるはずなのに閉路がある
・ありうる辺の上限よりもMが大きい、もしくは辺の下限N-1よりもMが小さい
"""

for a,b in multi:
    if root_find(a) == root_find(b):
        print("No")
        exit(0)
        
k = 0
for i in range(n):
    if root_find(i) == i:
        k += 1



if len(multi) > 0:
    min_edge = n

else:
    min_edge = n - 1

max_edge = n + k * (k - 3) // 2

if min_edge <= m <= max_edge:
    print("Yes")
else:
    print("No")

Solution (Python):
class UnionFindNode:
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1
        self.member_num_ = 1

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.member_num_ = root.member_num_ + unite_root.member_num_
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.member_num_ = root.member_num_ + unite_root.member_num_


if __name__ == "__main__":
    N,M,Q=[int(i) for i in input().strip().split(" ")]
    node_list = [UnionFindNode(i) for i in range(N)]
    import sys
    es = set()
    for line in sys.stdin:
        x,y,z=[int(i) for i in line.strip().split(" ")]
        if z == 0:
            node_list[x].unite(node_list[y])
        else:
            es.add((x,y))
    if M == N-1:
        if len(es):
            print("No")
            sys.exit()
    for e in es:
        if node_list[e[0]].root() == node_list[e[1]].root():
            print("No")
            sys.exit()
    counter = 0
    b = 0
    for node in node_list:
        if node.is_root():
            counter += 1
            b += node.root().member_num_ - 1
    if M<=b+((counter)*(counter-1)//2):
        print("Yes")
    else:
        print("No")

Solution (Python):

n, m, q = [int(item) for item in input().split()]

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1] * 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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        return self.size[self.find(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
    
Forest = UnionFind(n)
circles = []
group_num = n
edge_num = 0
seen = set()
for i in range(q):
    a, b, c = [int(item) for item in input().split()]
    if a > b:
        a, b = b, a
    if (a, b, c) in seen:
        continue
    if c == 0:
        
        if not Forest.same_check(a, b):
            Forest.union(a, b)
            group_num -= 1
            edge_num += 1
    else:
        circles.append((a, b, c))
    seen.add((a, b, c))

for a, b, c in circles:
    
    if Forest.same_check(a, b):
        print("No")
        exit()
    
    
    

if len(circles) > 0:
    edge_min = edge_num + group_num
    edge_max = edge_num + group_num * (group_num - 1) // 2
else:
    edge_min = edge_num + group_num - 1
    edge_max = edge_num + group_num * (group_num - 1) // 2

if edge_min <= m <= edge_max:
    print("Yes")
else:
    print("No")

Solution (Python):

n, m, q = [int(item) for item in input().split()]

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1] * 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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        return self.size[self.find(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
    
Forest = UnionFind(n)
circles = []
group_num = n
edge_num = 0
seen = set()
for i in range(q):
    a, b, c = [int(item) for item in input().split()]
    if a > b:
        a, b = b, a
    if (a, b, c) in seen:
        continue
    if c == 0:
        
        if not Forest.same_check(a, b):
            Forest.union(a, b)
            group_num -= 1
            edge_num += 1
    else:
        circles.append((a, b, c))
    seen.add((a, b, c))

for a, b, c in circles:
    
    if Forest.same_check(a, b):
        print("No")
        exit()
    if group_num == 2:
        print("No")
        exit()

if len(circles) > 0:
    edge_min = edge_num + group_num
    edge_max = edge_num + group_num * (group_num - 1) // 2
else:
    edge_min = edge_num + group_num - 1
    edge_max = edge_num + group_num * (group_num - 1) // 2

if edge_min <= m <= edge_max:
    print("Yes")
else:
    print("No")

Solution (Python):
import sys
input = sys.stdin.readline

N,M,Q=map(int,input().split())
E=[list(map(int,input().split())) for i in range(Q)]



Group=[i for i in range(N)]

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):  
    if find(x) != find(y):
        Group[find(y)]=Group[find(x)]=min(find(y),find(x))

E1=[]
for a,b,x in E:
    if x==0:
        Union(a,b)
    else:
        E1.append((a,b))

Group=[find(i) for i in range(N)]

for a,b in E1:
    if Group[a]==Group[b]:
        print("No")
        sys.exit()

C=len(set(Group))

if len(E1)==0:
    if N-1<=M<=(N-C)+C*(C-1)//2:
        print("Yes")
    else:
        print("No")

else:
    if N<=M<=(N-C)+C*(C-1)//2:
        print("Yes")
    else:
        print("No")

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]
        self.l = size

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            self.l -= 1

            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n,m,q = LI()
    aa = [LI() for _ in range(q)]
    uf = UnionFind(n)
    t = 0
    cc = 0
    for a,b,c in aa:
        if c == 0:
            if uf.union(a,b):
                t += 1
        else:
            cc += 1

    for a,b,c in aa:
        if c == 0:
            continue
        if uf.find(a) == uf.find(b):
            return 'No'

    if m == n - 1:
        if cc == 0:
            return 'Yes'
        return 'No'

    if m <= n - uf.l + uf.l * (uf.l-1) // 2:
        return 'Yes'

    return 'No'


print(main())

Solution (Python):
import sys


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def connected_count(self):
        return sum(x < 0 for x in self.table)


n, m, q = list(map(int, input().split()))
uft = UnionFind(n)
hyper_paths = set()

for line in sys.stdin:
    a, b, c = list(map(int, line.split()))
    if c == 1:
        hyper_paths.add((a, b))
        continue
    uft.union(a, b)

for a, b in hyper_paths:
    if uft.find(a, b):
        print('No')
        exit()

cc = uft.connected_count()

min_m = n if len(hyper_paths) > 0 else n - 1
max_m = n - cc + cc * (cc - 1) // 2

print('Yes' if min_m <= m <= max_m else 'No')

Solution (Python):
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)


def solve_d(n, m, q, a_list, b_list, c_list):

    res = 'Yes'
    uf = UnionFind(n - 1)
    for i in range(q):
        if c_list[i] == 0:
            uf.union(a_list[i], b_list[i])

    for i in range(q):
        if c_list[i] == 1:
            if uf.same_check(a_list[i], b_list[i]):
                res = 'No'

    par_list = [0] * n
    for i in range(n):
        par_list[i] = uf.find(i)

    k = len(set(par_list))
    
    if max(c_list) == 0:
        min_m = n - 1
    else:
        min_m = n
    if m < min_m:
        res = 'No'
    elif m > n + k * (k - 3) // 2:
        res = 'No'

    return res


def main():
    n, m, q = map(int, input().split())
    a_list = [0] * q
    b_list = [0] * q
    c_list = [0] * q

    for i in range(q):
        a, b, c = map(int, input().split())
        a_list[i] = a
        b_list[i] = b
        c_list[i] = c

    res = solve_d(n, m, q, a_list, b_list, c_list)
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input=sys.stdin.readline

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 x==y:
            return
        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)

def main():
    n,m,q=map(int,input().split())
    E=[]
    uf=UnionFind(n)
    for _ in range(q):
        a,b,c=map(int,input().split())
        if c:
            E.append((a,b)) 
        else:
            uf.union(a,b)
    s=set()
    for i in range(n):
        s.add(uf.find(i))
    k=len(s)
    if E and (k<=2 or m==n-1):
        print('No')
        return
    for a,b in E:
        if uf.same_check(a,b):
            print('No')
            return
    print('Yes' if m<=n+k*(k-3)//2 else 'No')

if __name__=='__main__':
    main()

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [-1 for i in range(n+1)]
        self.rank = [0] * (n+1)
 
    
    def find(self, x):
        if self.par[x] < 0:
            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 not x==y: 
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x] 
                self.par[x] = y 
            else:
                self.par[x] += self.par[y]
                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) 
 
def main():
    import sys
    input = sys.stdin.readline
    
    N,M,Q = map(int,input().split())
    KI = UnionFind(N-1)
    CC = []
    for i in range(Q):
        A,B,C = map(int,input().split())
        if C == 0:
            KI.union(A,B)
        else:
            CC.append([A,B])
    
    flag = 0
    
    oya = {}
    for i in range(N):
        p = KI.find(i)
        oya[p]=1
    PPP = len(oya)
    
    for i in CC:
        A,B = i
        if KI.same_check(A,B):
            flag = 1
            break
        elif PPP<=2:
            flag = 1
            break
        elif M == N-1:
            flag = 1
            break
    
    if N-1+((PPP-2)*(PPP-1))//2 < M:
        flag = 1
            
    if flag == 0:
        print("Yes")
    else:
        print("No")
    
    
    
    
main()