Problem:


Score : 400 points

Problem Statement

There are N people standing on the x-axis.
Let the coordinate of Person i be x_i.
For every i, x_i is an integer between 0 and 10^9 (inclusive).
It is possible that more than one person is standing at the same coordinate.

You will given M pieces of information regarding the positions of these people.
The i-th piece of information has the form (L_i, R_i, D_i).
This means that Person R_i is to the right of Person L_i by D_i units of distance, that is, x_{R_i} - x_{L_i} = D_i holds.

It turns out that some of these M pieces of information may be incorrect.
Determine if there exists a set of values (x_1, x_2, ..., x_N) that is consistent with the given pieces of information.

Constraints

1 \leq N \leq 100 000

0 \leq M \leq 200 000

1 \leq L_i, R_i \leq N (1 \leq i \leq M)

0 \leq D_i \leq 10 000 (1 \leq i \leq M)

L_i \neq R_i (1 \leq i \leq M)

If i \neq j, then (L_i, R_i) \neq (L_j, R_j) and (L_i, R_i) \neq (R_j, L_j).

D_i are integers.

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 D_1
L_2 R_2 D_2
:
L_M R_M D_M

Output

If there exists a set of values (x_1, x_2, ..., x_N) that is consistent with all given pieces of information, print Yes; if it does not exist, print No.

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 1

Yes

Some possible sets of values (x_1, x_2, x_3) are (0, 1, 2) and (101, 102, 103).

Sample Input 2

3 3
1 2 1
2 3 1
1 3 5

Sample Output 2

No

If the first two pieces of information are correct, x_3 - x_1 = 2 holds, which is contradictory to the last piece of information.

Sample Input 3

4 3
2 1 1
2 3 5
3 4 2

Sample Output 3

Yes

Sample Input 4

10 3
8 7 100
7 9 100
9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes



Sample input:
3 3
1 2 1
2 3 1
1 3 2


Sample output:
Yes

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        self.weight = [0]*(n+1)
 
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            r = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            self.root[x] = r
            return r

    def GetWeight(self, x):
      self.Find_Root(x)
      return self.weight[x]

    def Unite(self, x, y, w):
        w += self.GetWeight(x)
        w -= self.GetWeight(y)
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return False

        if self.rnk[x] < self.rnk[y]:
            x, y = y, x
            w = -w
        if self.rnk[x] == self.rnk[y]:
            self.rnk[x] += 1
        
        self.root[y] = x
        self.weight[y] = w

        return True
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
        return self.GetWeight(y) - self.GetWeight(x)

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  for i in range(M):
    l, r, d = lrd[i]
    if not U.isSameGroup(l, r):
      U.Unite(l, r, d)
    else:
      if U.Diff(l, r) != d:
        print('No')
        exit()
  print('Yes')
  
    
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


union = UnionFind(N-1)

graph = [[] for _ in range(N)]
for _ in range(M):
    a, b, d = map(int, input().split())
    graph[a-1].append((d, b-1))
    graph[b-1].append((-d, a-1))
    union.Unite(a-1, b-1)

roots = set()
for i in range(N):
    roots.add(union.Find_Root(i))

NUM = [None for _ in range(N)]
checked = [False for _ in range(N)]

def dfs(p, NUM, ans):
    x = NUM[p]
    for d, q in graph[p]:
        #print(p, q, NUM, d, x)
        if NUM[q] is None:
            NUM[q] = x+d
        elif NUM[q] != x+d:
            #print("different!!")
            ans = False
            return ans
        if checked[q]:
            continue
        checked[q] = True
        ans = dfs(q, NUM, ans)
    return ans

ans = True
for r in roots:
    NUM[r] = 0
    ok = dfs(r, NUM, True)
    ans = ans and ok

if ans:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()


N, M = list(map(int, input().split()))
default = 100000000000000000000000

graph = [[] for _ in range(N)]
dist = [default for _ in range(N)]

for i in range(M):
	L, R, D = list(map(int, input().split()))
	L -= 1
	R -= 1
	graph[L].append([R, D])
	graph[R].append([L, -D])

loc = 0
while loc < N:
	if dist[loc] == default:
		dist[loc] = 0
		que = deque([])
		que.append(loc)
		while len(que) > 0:
			node = que.popleft()
			if len(graph[node]) > 0:
				for edge in graph[node]:
					if dist[edge[0]] == default:
						dist[edge[0]] = dist[node] + edge[1]
						que.append(edge[0])
					elif dist[edge[0]] != dist[node] + edge[1]:
						print("No")
						exit()
	loc += 1
print("Yes")

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
par=[i for i in range(n)]
ws =[0 for _ in range(n)]

def root(x):
    if par[x]==x:
        return x
    else:
        r =root(par[x])
        ws[x] +=ws[par[x]]
        par[x]=r
        return par[x]

def weight(x):
    root(x)
    return ws[x]
def diff(x,y):
    return weight(x) -weight(y)

def merge(x,y,w):
    if root(x)==root(y):
        if diff(x,y)!=w:
            print('No')
            exit()
        else:
            return
    else:
        wy=weight(y)
        wx=weight(x)
        x=root(x)
        y=root(y)
        if w+wy>=wx:
            
            par[x]=y
            ws[x]=w+wy-wx
        else:
            par[y]=x
            ws[y]=wx-w-wy

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

print('Yes')

Submission status: Accepted

Solution code:
from collections import deque



def main():
    n, m = map(int, input().split())
    graph = [[] for i in range(n)]
    for _ in range(m):
        l, r, d = map(int, input().split())
        graph[l - 1] += [(r - 1, d)]
        graph[r - 1] += [(l - 1, -d)]


    que = deque()
    lines = [None] * n


    for i in range(n):
        if lines[i] is not None:
            continue
        lines[i] = 0
        que.append(i)
        while que:
            cur = que.popleft()
            for nxt, cost in graph[cur]:
                if lines[nxt] is None:
                    lines[nxt] = lines[cur] + cost
                    que.append(nxt)
                else:
                    if lines[nxt] != lines[cur] + cost:
                        return 'No'
    return 'Yes'



print(main())

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math

def calc(A, B, C, now_t):
    ans = A * now_t + B * math.sin(C * now_t * math.pi)
    return ans


def main():
    num, hint_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(hint_num)]

    graph_data = defaultdict(set)
    dist_data = defaultdict(int)

    for i in range(hint_num):
        l, r , d = data[i]
        graph_data[l].add(r)
        graph_data[r].add(l)
        dist_data[(l, r)] = d
        dist_data[(r, l)] = -1 * d


    position = ['x' for i in range(num + 1)]
    flg = 1
    for i in range(1, num + 1):
        if position[i] != 'x':
            continue
        position[i] = 0
        now_set = set()
        next_set = set()
        now_set.add(i)

        while len(now_set) > 0:
            for now_ele in now_set:
                for next_ele in graph_data[now_ele]:
                    length = dist_data[(now_ele, next_ele)]
                    if position[next_ele] == 'x':
                        position[next_ele] = position[now_ele] + length
                        next_set.add(next_ele)
                    else:
                        if position[next_ele] != position[now_ele] + length:
                            flg = 0
                            break
            now_set = next_set
            next_set = set()

    # print(position)

    if flg:
        print('Yes')
    else:
        print('No')





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict, deque

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, adj):
    visited = [False] * N
    pos = [None] * N

    for i, vis in enumerate(visited):
        if vis:
            continue
        pos[i] = 0
        visited[i] = True
        Q = deque([i], M)
        while len(Q) > 0:
            u = Q.popleft()
            for v, d in adj[u]:
                if pos[v] is None:
                    pos[v] = pos[u] + d
                elif pos[v] != pos[u] + d:
                    print(NO)
                    return

                if visited[v]:
                    continue
                Q.append(v)
                visited[v] = True
    print(YES)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    adj = [set() for _ in range(N)]
    for i in range(M):
        l = int(next(tokens)) - 1
        r = int(next(tokens)) - 1
        d = int(next(tokens))
        adj[l].add((r, d))
        adj[r].add((l, -d))
    solve(N, M, adj)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
lines = [None] * N
stack = [0]
edges = [[] for _ in range(N)]
for _ in range(M):
    l, r, d = map(int, input().split())
    edges[l-1].append((r-1, d))
    edges[r-1].append((l-1, -d))

for i in range(N):
    if lines[i] is not None:
        continue
    lines[i] = 0
    stack = [i]
    while stack:
        v = stack.pop()
        for u, d in edges[v]:
            if lines[u] is None:
                lines[u] = lines[v] + d
                stack.append(u)
            elif lines[v] + d != lines[u]:
                print("No")
                quit()

print("Yes")

Submission status: Accepted

Solution code:
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
    
    
n,m = map(int,input().split())
uf = WeightedUnionFind(n)
ans = True
for i in range(m):
    l,r,d = map(int,input().split())
    if uf.same(l,r)==False:
        uf.union(l,r,d)
    else:
        if abs(uf.diff(l,r))!=d:
            ans = False
            break
print("Yes" if ans else "No")

Submission status: Accepted

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

class WeightedUnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n
        self.weight = [0] * n
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y
        
    def unite(self, x, y, w):
        px = self.find(x)
        py = self.find(y)
        
        if px == py:
            return True
        
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        elif self.rank[px] < self.rank[py]:
            px, py = py, px
            x, y = y, x
            w *= -1

        self.par[py] = px
        self.weight[py] = self.weight[x] - self.weight[y] - w
                
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

t = WeightedUnionFind(N + 1)
for l, r, d in X:
    if t.same(l, r):
        if t.diff(l, r) != d:
            print('No')
            break
    else:
        t.unite(l, r, d)
else:
    print('Yes')

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
N,M=map(int,input().split())
P=[list(map(int,input().split())) for i in range(M)]
inf=10**15
c=[[] for i in range(N)]
for i,j,w in P:
    c[i-1].append((j-1,w))
    c[j-1].append((i-1,-w))
d=[inf]*N
v=[0]*N
a=0
import sys
sys.setrecursionlimit(10**7)
def dfs(p,v,d):
    for n,w in c[p]:
        if v[n]==0:
            d[n]=d[p]+w
            v[n]=1
            if dfs(n,v,d)==-1:
                return -1
        elif d[p]+w!=d[n]:
            return -1
    return 0
s=0
while True:
    d[s]=0
    v[s]=1
    a=dfs(s,v,d)
    if a<0:
        break
    try:
        s=d.index(inf,s)
    except ValueError:
        break
print(['Yes','No'][a])

Submission status: Accepted

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

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

for i in range(M) :
    l,r,d = map(int,input().split())
    
    l -= 1
    r -= 1
    
    A[l].append([r,d])
    A[r].append([l,-d])
    
ans = "Yes"

distance = ["#" for i in range(N)]

flg = 0

for i in range(N) :
    if flg :
        break
    
    if distance[i] != "#" :
        continue
    
    distance[i] = 0
    stack = [i]
    
    while stack :
        now = stack.pop()
        
        for to,d in A[now] :
            if distance[to] == "#" :
                distance[to] = distance[now] + d
                stack.append(to)
            
            elif distance[to] != distance[now] + d :
                ans = "No"
                stack = []
                flg = 1
                break
            
print(ans)

Submission status: Accepted

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

for i in range(M) :
    l,r,d = map(int,input().split())
    
    l -= 1
    r -= 1
    
    A[l].append([r,d])
    A[r].append([l,-d])

distance = ["#" for i in range(N)]

ans = "Yes"

flg = 0

for i in range(N) :
    if flg == 1 :
        break
    
    if distance[i] != "#" :
        continue
    
    distance[i] = 0
    stack = [i]
    
    while stack :
        v = stack.pop()
        
        for to,d in A[v] :
            if distance[to] == "#" :
                distance[to] = distance[v] + d
                stack.append(to)
            
            elif distance[to] != distance[v] + d :
                ans = "No"
                stack = []
                flg = 1
                break
                

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


class WeightedUnionFind:
    def __init__(self, node: int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        self.diff_weight = [0 for i in range(self.n)]

    # ノードxのルートを求める
    def find(self, x: int) -> int:
        if x == self.par[x]:
            return x
        else:
            r = self.find(self.par[x])
            self.diff_weight[x] += self.diff_weight[self.par[x]]
            self.par[x] = r
            return self.par[x]

    # ノードxのルートからの距離を求める
    def weight(self, x: int) -> int:
        self.find(x)
        return self.diff_weight[x]

    # weight(y) - weight(x) = w となるようにする
    def unite(self, x: int, y: int, w: int) -> bool:
        if self.isSame(x, y):
            # print("x and y has already united")
            return False

        w += self.weight(x)
        w -= self.weight(y)

        rx = self.find(x)
        ry = self.find(y)

        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
            w = -w

        self.par[ry] = self.par[rx]
        self.diff_weight[ry] = w

        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1

        return True

    def isSame(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def diff(self, x: int, y: int) -> int:
        if self.isSame(x, y):
            return self.weight(y) - self.weight(x)
        else:
            raise ValueError("xとyは同じ木に属していません")


def judge(wuf, state):
    for l, r, d in state:
        if wuf.diff(l, r) != d:
            return False

    return True


n, m = li()
wuf = WeightedUnionFind(n)

lrd = []

for _ in range(m):
    l, r, d = li()
    l -= 1
    r -= 1

    lrd.append((l,r,d))

    wuf.unite(l, r, d)

print("Yes" if judge(wuf, lrd) else "No")

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
class PotUnionFind:
    __slots__ = ["parent", "gsize", "diff_p"]
    def __init__(self, n):
        self.parent = list(range(n)) #親ノード
        self.gsize = [1]*n #グループの要素数
        self.diff_p = [0]*n #親ノードを基準としたポテンシャル
 
    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            self.diff_p[x] += self.diff_p[self.parent[x]]
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 

    def weight(self, x): #root(x): xの根ノードを返す．
        c=0
        while self.parent[x] != x:
            self.diff_p[x] += self.diff_p[self.parent[x]]
            self.parent[x] = self.parent[self.parent[x]]
            c += self.diff_p[x]
            x = self.parent[x]
        return c


    def merge(self, x, y, dxy): #ポテンシャル差p(y)-p(x)=dxyでxとyの組をまとめる
        dxy += self.weight(x) - self.weight(y) #dxyをで置き換え
        x,y = self.root(x), self.root(y)
        if x == y: return False
        if self.gsize[x] > self.gsize[y]: #rxの要素数が大きいように
            x,y,dxy = y,x,-dxy
        self.gsize[x] += self.gsize[y] #xの要素数を更新
        self.parent[y] = x #ryをrxにつなぐ
        self.diff_p[y] = dxy #ryの相対ポテンシャルを更新
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じ組ならTrue
        return self.root(x) == self.root(y)
        
    def diff(self,x,y): #diff(x,y): xを基準としたyのポテンシャルを返す 
        if self.root(x) == self.root(y):
            return self.weight(y) - self.weight(x)
        else:
            return None

    def size(self,x): #size(x): xのいるグループの要素数を返す
        return self.gsize[self.root(x)]


n,m = list(map(int,input().split()))
 
uf = PotUnionFind(n)
ans = True
for i in range(m):
    l,r,d=list(map(int,input().split()))
    l-=1;r-=1;
    if uf.issame(l,r):
        ans = d==uf.diff(l,r)
    else:
        uf.merge(l,r,d)
    if ans == False:
        break
 
if ans == False:
    print('No')
else:
    print('Yes')

Submission status: Accepted

Solution code:
# 重み付きUnion-Findデータ構造
class WeightedUnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
        self.weights = [0] * numV

    def find(self, x):
        if self.pars[x] == x:
            return x
        else:
            parXOld = self.pars[x]
            self.pars[x] = self.find(parXOld)
            self.weights[x] += self.weights[parXOld]
            return self.pars[x]

    def union(self, x, y, wt):
        wtX = self.getWeight(x)
        wtY = self.getWeight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return wtY == wtX+wt
        wt += wtX - wtY
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
            self.weights[x] = -wt
        else:
            self.pars[y] = x
            self.weights[y] = wt
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
        return True

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

    def getWeight(self, x):
        self.find(x)
        return self.weights[x]

    def getDiff(self, x, y):
        if self.find(x) == self.find(y):
            return self.getWeight(y) - self.getWeight(x)
        else:
            return float('inf')


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

WUF = WeightedUnionFind(N)
ans = 'Yes'
for _ in range(M):
    L, R, D = map(int, input().split())
    if not WUF.union(L-1, R-1, D):
        ans = 'No'

print(ans)

Submission status: Accepted

Solution code:
from collections import*
class POTENTIAL_UNION_FIND(object):
    def __init__(self, n):
        self.parent = [-1 for i in range(n)]#非負なら親ノード，負ならグループの要素数
        self.diff_p = [0 for i in range(n)]#親ノードを基準としたポテンシャル
 
    def root(self, x): #root(x): xの根ノードを返す
        if self.parent[x] < 0:
            return x
        else:
            rx = self.root(self.parent[x]) #xをxの根rxに直接つなぎたい
            self.diff_p[x] += self.diff_p[self.parent[x]] #そのために，diff(rx,x)を計算
            self.parent[x] = rx #xをrxに直接つなげる
            return rx
 
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]

    def merge(self, x, y, dxy): #ポテンシャル差の条件p(y)-p(x)=dxyでxとyのグループをまとめる
        rx = self.root(x) #rxを新たにxと名づける
        ry = self.root(y) #ryを新たにyと名づける
        dxy += self.diff_p[x] - self.diff_p[y] #dxyをdiff(rx,ry)で置き換え
        x,y=rx,ry
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y,dxy=y,x,-dxy
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        self.diff_p[y] = dxy #yの相対ポテンシャルを更新
        return True
 
    def issame(self, x, y): #issame(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def diff(self,x,y): #diff(x,y): xを基準としたyのポテンシャルを返す 
        if self.root(x) == self.root(y): #この時点でxの親はroot(x)
            return self.diff_p[y] - self.diff_p[x]
        else:
            return None


n,m=map(int,input().split())
u=POTENTIAL_UNION_FIND(n)
d=defaultdict(int)
for i in range(m):
    a,b,c=map(int,input().split())
    d[(a-1,b-1)]=c
    u.merge(a-1,b-1,c)
for k,v in d.items():
    if v!=u.diff(*k):
        print("No")
        exit()
print("Yes")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, sys.stdin.readline().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, q = map(int, sys.stdin.readline().split())
    G[l - 1].append((r - 1, q))
    G[r - 1].append((l - 1, -q))

R = [None] * N


def dfs(u):
    global R, G
    for w, d in G[u]:
        if R[w] is None:
            R[w] = R[u] + d
            if not dfs(w):
                return False
        else:
            if R[w] != R[u] + d:
                return False
    return True


flag = True
for i in range(N):
    if R[i] is None:
        R[i] = 0
        flag &= dfs(i)

if flag:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys


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

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]


n, m = list(map(int, input().split()))
wuf = WeightedUnionFind(n + 1)

for _ in range(m):
    l, r, d = list(map(int, input().split()))

    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            sys.exit()
    wuf.union(l, r, d)

print("Yes")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

n,m = map(int,input().split())
edge = [[] for i in range(n)]
for i in range(m):
    l,r,d = map(int, input().split())
    edge[l-1].append((r-1,d))
    edge[r-1].append((l-1,-d))

dist = [0]*n
visited = [False]*n

for i in range(n):
    if visited[i]:
        continue
    q = deque()
    q.append((i,0))
    while q:
        to, d = q.popleft()
        if visited[to]:
            if dist[to] != d:
                print("No")
                exit()
        else:
            visited[to] = True
            dist[to] = d
            for ind, j in edge[to]:
                q.append((ind,d+j))

print("Yes")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ed = [[] for _ in range(n)]  # グラフ
v = [None] * n
for _ in range(m):
  l, r, d = map(int, input().split())
  ed[l-1].append((r-1, d))  # l -> r
  ed[r-1].append((l-1, -d))  # r -> l

visited = [False] * n  # 訪問フラグ（非連結の可能性の為）

def dfs(start):
  s = [start]
  v[start] = 0
  while s:
    label = s.pop()
    if visited[label] == False:
      visited[label] = True
      for to, dist in ed[label]:
        if v[to] is None:
          v[to] = v[label] + dist
          s.append(to)
        else:
          if v[to] != v[label] + dist:
            return False
  return True

is_exist = True
for i in range(n):
  if v[i] is None:
    if not dfs(i):
      print('No')
      is_exist = False
      break
if is_exist:
  print("Yes")

Submission status: Accepted

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

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def unite(self, x, y, w):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] < self.rank[py]:
                self.par[px] = py
                self.weight[px] = w - self.weight[x] + self.weight[y]
            else:
                self.par[py] = px
                self.weight[py] = -w - self.weight[y] + self.weight[x]
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1

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

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]


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

graph = WeightedUnionFind(N)
for l, r, d in LRD:
    l -= 1
    r -= 1
    if graph.are_same(l, r):
        if graph.diff(l, r) != d:
            print("No")
            break
    else:
        graph.unite(l, r, d)
else:
    print("Yes")

Submission status: Accepted

Solution code:
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from scipy.sparse.csgraph import floyd_warshall as wf
INF = float("inf")


N,M = map(int,input().split())
Adj_list = defaultdict(set)

for i in range(M):
    a, b, c = map(int, input().split())
    Adj_list[a-1].add((b-1, c))
    Adj_list[b-1].add((a-1, -c))
visited =[None]*(N)
ok = True
stack = []
for x in range(N):
   if visited[x] is not None:continue
   visited[x] = 0
   stack = [x]
   while stack:
       v = stack.pop()
       for to,d in Adj_list[v]:
           if visited[to] is None:
               visited[to] = visited[v] + d
               stack.append(to)
           else:
               if visited[to] != visited[v]+d:
                   ok = False
                   break
   if ok == False:
        break
print("Yes" if ok else "No")