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
input = sys.stdin.readline
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            px = find(par[x])
            wei[x] += wei[par[x]]
            par[x] = px
            return px

    def weight(x):
        find(x)
        return wei[x]

    def unite(x, y, w):
        w += wei[x] - wei[y]
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            # sizeの大きいほうがx
            if par[x] > par[y]:
                x, y = y, x
                w = -w
            par[x] += par[y]
            par[y] = x
            wei[y] = w
            return True

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

    def size(x):
        return -par[find(x)]

    def diff(x, y):
        return weight(y) - weight(x)

    n, m = map(int, input().split())
    # 初期化
    par = [-1] * n
    wei = [0] * n
    for _ in range(m):
        l, r, d = map(int, input().split())
        l -= 1
        r -= 1
        if same(l, r):
            if diff(l, r) != d:
                print('No')
                sys.exit()
        else:
            unite(l, r, d)
    print('Yes')
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  # 親のノード番号
        self.rank = [0]*(n+1)
        self.diff_weight = [0]*(n+1)  # 親ノードとのweightの差
    def root(self,x):  # xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            r = self.root(self.par[x])
            self.diff_weight[x] += self.diff_weight[self.par[x]]
            self.par[x] = r
            return self.par[x]
    def same_check(self,x,y):  # x,yが同じグループか否か
        return self.root(x) == self.root(y)
    def weight(self,x):
        r = self.root(x)  # 経路圧縮
        return self.diff_weight[x]
    def diff(self,x,y):
        return self.weight(y) - self.weight(x)
    def unite(self,x,y,w):  # x,yの属するグループの併合
        w += self.weight(x)
        w -= self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if self.rank[x] < self.rank[y]:
            x,y = y,x
            w = -w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x
        self.diff_weight[y] = w

import sys

sys.setrecursionlimit(10**7)
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def S(): return sys.stdin.readline().rstrip()

N,M = map(int,S().split())
G = UnionFind(N)
for i in range(M):
    L,R,D = LI()
    if G.same_check(L,R):
        if G.diff(L,R) != D:
            print('No')
            exit()
    else:
        G.unite(L,R,D)

print('Yes')

Submission status: Accepted

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

def bfs(s):
    que = deque([(0, s)])
    while que:
        d, v = que.popleft()
        if visited[v]:
            if d != dist[v]:
                return False
            continue
        visited[v] = True
        dist[v] = d
        for w, u in A[v]:
            que.append((d + w, u))
    return True

N, M = map(int, input().split())
A = [[] for _ in range(N)]
for _ in range(M):
    l, r, w = map(int, input().split())
    l -= 1
    r -= 1
    A[l].append((w, r))
    A[r].append((-w, l))
visited = [0] * N
dist = [0] * N
res = 'Yes'
for i in range(N):
    if visited[i]:
        continue
    f = bfs(i)
    if not f:
        res = 'No'
print(res)

Submission status: Accepted

Solution code:
"""
unite時に矛盾しないかどうかを判定させる。
同じ木の中では、より右にいるノードを親とする。
親との距離をどこかに記録しておく。
"""
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.dict = [0]*(N+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.find(self.parents[x])
            u = self.dict[self.parents[x]]
            self.parents[x]=self.find(self.parents[x])
            #xのdictを更新する。
            self.dict[x] += u
            return self.parents[x]
    def unite(self,x,y,d):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            if self.dict[x]-self.dict[y]!=d:
                print("No")
                exit()
        #より右にいるノードを親にする
        if self.dict[y]+d > self.dict[x]:
            self.parents[xRoot] = yRoot
            self.dict[xRoot] = self.dict[y]+d-self.dict[x]
        else:
            self.parents[yRoot] = xRoot
            self.dict[yRoot] = self.dict[x]-(self.dict[y]+d)

N,M = map(int,input().split())
tree = UnionFind(N)
for _ in range(M):
    l,r,d = map(int,input().split())
    tree.unite(l,r,d)
print("Yes")

Submission status: Accepted

Solution code:
from collections import deque

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

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

dist = [int(1e10)] * N

def bfs(id):
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()

        for edge in graph[v]:
            u, d = edge[0], edge[1]

            if dist[u] == int(1e10):
                dist[u] = dist[v] + d
                Q.append(u)
            elif dist[u] != dist[v] + d:
                print("No")
                exit()


for i in range(N):
    if dist[i] == int(1e10):
        bfs(i)

print("Yes")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
class UFP():
    def __init__(self, num):
        self.par = [-1]*num
        self.dist = [0]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            res = 0
            xo = x
            while self.par[x] >= 0:
                res += self.dist[x]
                x = self.par[x]
            self.dist[xo] = res
            self.par[xo] = x
            return x
    
    def union(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] > self.par[ry]:
                rx, ry = ry, rx
                x, y = y, x
                d = -d
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
            self.dist[ry] = d + self.dist[x] - self.dist[y]
            return True
        else:
            if d + self.dist[x] - self.dist[y]:
                return False
            return True

N, M = map(int, readline().split())
T = UFP(N)
ans = 'No'
for _ in range(M):
    l, r, d = map(int, readline().split())
    l -= 1
    r -= 1
    if not T.union(l, r, d):
        break
else:
    ans = 'Yes'
print(ans)

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, N):
    self.parents = [-1] * (N+1)
    self.weight = [0] * (N+1)

  def union(self, f, t, w):
    w += self.weight[f]
    w -= self.weight[t]

    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return

    if self.parents[p1] > self.parents[p2]:
      p1,p2 = p2,p1
      w = -w
    self.parents[p1] += self.parents[p2]
    self.weight[p2] = w
    self.parents[p2] = p1

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

  def compare_weight(self, x, y):
    self.find(x); self.find(y)
    return abs(self.weight[y] - self.weight[x])

  def same(self, n1, n2):
    # import pdb; pdb.set_trace()
    return self.find(n1) == self.find(n2)

N,M = map(int, input().split())
uf = UF(N)
flg = True
for _ in range(M):
  l,r,d = map(int, input().split())
  if uf.same(l, r):
    if uf.compare_weight(l,r) != d:
      flg = False
      break
  else:
    uf.union(l,r,d)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        #dist[x]はxとその親との間の距離を保持している
        self.dist = [0]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            a = self.parents[x]
            self.parents[x]=self.find(self.parents[x])
            self.dist[x] += self.dist[a]
            return self.parents[x]
    def unite(self,l,r,d):
        rRoot = self.find(r)
        lRoot = self.find(l)
        if rRoot == lRoot:
            if self.dist[l] - self.dist[r] != d:
                print("No")
                exit()
        else:
            #rRootとlRoot、どちらが親になるべきか決める
            newLDist = d + self.dist[r]
            if newLDist>=self.dist[l]:
                self.parents[lRoot] = rRoot
                self.dist[lRoot] = newLDist-self.dist[l]
            else:
                self.parents[rRoot] = lRoot
                self.dist[rRoot] = self.dist[l]-newLDist

N,M = map(int,input().split())
tree = UnionFind(N)
for _ in range(M):
    l,r,d = map(int,input().split())
    tree.unite(l,r,d)
print("Yes")

Submission status: Accepted

Solution code:
class WeightedUnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        # 親ノードとの重み
        self.diff_weight = [0 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        # 親ノードはまだ上書きしない
        root = self.find(self.par[x])
        self.diff_weight[x] += self.diff_weight[self.par[x]]
        self.par[x] = root
        return self.par[x]

    def weight(self, x):
        """ x 根に対する重みを返す """
        self.find(x)
        return self.diff_weight[x]

    def diff(self, x, y):
        """ x と y の差分をとる """
        return self.weight(y) - self.weight(x)

    def unite(self, x, y, w):
        """ ノード x の下にノード y をつける。辺の重みは、w """
        # ただし、実際には、x の根と y の 根をくっつけるので、補正
        w += self.weight(x); w -= self.weight(y)
        x = self.find(x); y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            # y の下に x をつけることになるので、重さは反転させる
            self.par[x] = y
            w = -w
            self.diff_weight[x] = w
        elif self.rank[y] < self.rank[x]:
            self.par[y] = x
            self.diff_weight[y] = w
        else:
            self.par[y] = x
            self.rank[x] += 1
            self.diff_weight[y] = w
            
N, M = map(int, input().split())
UF = WeightedUnionFind(N)
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    # これまでに入力されたものと等しくないか確認する
    if UF.find(L) == UF.find(R):
        if UF.diff(L, R) != D:
            print('No')
            break
    else:
        UF.unite(L, R, D)
else:
    print('Yes')

Submission status: Accepted

Solution code:
"""
unionFind木を使う。
根に対する距離を記録していく。
"""
import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.distance = [0]*(n+1)

    def find(self,x):
        if self.parents[x]==x:
            return x,0
        else:
            self.parents[x],dist2=self.find(self.parents[x])
            self.distance[x] += dist2
            return self.parents[x],self.distance[x]

    def union(self,l,r,dist):
        lRoot,lDist = self.find(l)
        rRoot,rDist = self.find(r)
        #まず、位置関係に矛盾がないかを調べる
        #lRootはlよりlDist右にいる
        #rRootはrよりrDist右にいる
        #lRoot=rRootのとき、lDist-rDist != distなら矛盾。
        if lRoot==rRoot and lDist-rDist != dist:
            print("No")
            exit()

        #より左にいる根を右にいる根にマージする
        if lDist < dist+rDist:
            #lRootがrRootよりも左の場合
            self.parents[lRoot]=rRoot
            self.distance[lRoot]=(dist+rDist)-lDist
        else:
            self.parents[rRoot]=lRoot
            self.distance[rRoot]=lDist-(dist+rDist)

N,M = map(int,input().split())
tree = UnionFind(N)
for i in range(M):
    L,R,D = map(int,input().split())
    tree.union(L,R,D)

print('Yes')

Submission status: Accepted

Solution code:
class WeightedUnionFind:

    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.weights = [0 for _ in range(n + 1)]
        self.ranks = [0 for _ in range(n + 1)]

    def find_root(self, node):
        parent_node = self.parents[node]
        if node == parent_node:
            return node
        else:
            root_node = self.find_root(parent_node)
            # reduction
            self.parents[node] = root_node
            self.weights[node] += self.weights[parent_node]
            return root_node

    def union(self, one, other, weight):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        if one_root == other_root:
            return
        one_rank = self.ranks[one_root]
        other_rank = self.ranks[other_root]
        diff_weight = weight + self.weights[one] - self.weights[other]
        if one_rank < other_rank:
            self.parents[one_root] = other_root
            # modify weight s.t. weight(one) + weight = weight(other)
            self.weights[one_root] -= diff_weight
        else:
            self.parents[other_root] = one_root
            # modify weight s.t. weight(one) + weight = weight(other)
            self.weights[other_root] += diff_weight
            if one_rank == other_rank:
                self.ranks[other_root] += 1

    def is_same_group(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        return one_root == other_root

    def diff(self, one, other):
        if not self.is_same_group(one, other):
            return None
        return self.weights[other] - self.weights[one]


def main():
    N, M = list(map(int, input().split(' ')))
    tree = WeightedUnionFind(N)
    for _ in range(M):
        L, R, D = list(map(int, input().split(' ')))
        d = tree.diff(L, R)
        if d is None:
            tree.union(L, R, D)
            continue
        # print(tree.parents)
        # print(tree.weights)
        if d != D:
            print('No')
            exit(0)
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

INF=10**9
N,M=map(int,input().split())

def dfs(u,d1):
  pos_list[u]=d1
  for v,d2 in graph[u]:
    if pos_list[v]==-INF:
      dfs(v,d1+d2)
    elif pos_list[v]!=d1+d2:
      print("No")
      sys.exit(0)      
  return

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

pos_list=[-INF]*(N+1)
for i in range(1,N+1):
  if pos_list[i]!=-INF:
    continue
  dfs(i,0)
          
#print(pos_list[1:])
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]

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
uf=WeightedUnionFind(N)
for i in range(0,M):
    l,r,d=map(int,input().split())
    if uf.same(l,r):
        if d!=uf.diff(l,r):
            print('No')
            break
    else:
        uf.union(l,r,d)
else:
    print('Yes')

Submission status: Accepted

Solution code:
#!python3

import sys
sys.setrecursionlimit(200000)


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


def judge(W, D, visit, i):
    visit[i] = True
    for j, d in W[i]:
        if D[j] is None:
            D[j] = D[i] + d
        else:
            if D[i] + d != D[j]:
                return True
        if visit[j]:
            continue
        if judge(W, D, visit, j):
            return True
    
    return False


def main():
    W = [[] for _ in range(N)]
    for l, r, d in LRD:
        W[l - 1].append((r - 1, d))
        W[r - 1].append((l - 1, -d))
    
    D = [None] * N
    visit = [False] * N
    for i in range(N):
        if visit[i]:
            continue
        D[i] = 0
        if judge(W, D, visit, i):
            print("No")
            return
    
    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Accepted

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

INF=10**9
N,M=map(int,input().split())

def dfs(u,d1):
  pos_list[u]=d1
  for v,d2 in graph[u]:
    if pos_list[v]==-INF:
      dfs(v,d1+d2)
    elif pos_list[v]!=d1+d2:
      print("No")
      sys.exit(0)      
  return

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

pos_list=[-INF]*(N+1)
for i in range(1,N+1):
  if pos_list[i]!=-INF:
    continue
  dfs(i,0)
          
#print(pos_list[1:])
print("Yes")

Submission status: Accepted

Solution code:
import sys
INF=10**9
N,M=map(int,input().split())

graph=[]
for i in range(N+1):
  graph.append([])

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

pos_list=[-INF]*(N+1)
for i in range(1,N+1):
  if pos_list[i]!=-INF:
    continue
    
  queue={i}
  pos_list[i]=0
  while(len(queue)>0):
    new_queue=set()
    for q in queue:
      for v,d in graph[q]:
        if pos_list[v]==-INF:
          pos_list[v]=pos_list[q]+d
          new_queue.add(v)
        elif pos_list[v]!=pos_list[q]+d:
          print("No")
          sys.exit(0)
          
    queue=new_queue
          
#print(pos_list[1:])
print("Yes")

Submission status: Accepted

Solution code:
from sys import exit

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

    def find(self, x):
        if self.parent[x] == x:
            return x
        nx = self.find(self.parent[x])
        self.weights[x] += self.weights[self.parent[x]]
        self.parent[x] = nx
        return nx

    def unite(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
            self.weights[rx] = d + self.weights[y] - self.weights[x]
        else:
            self.parent[ry] = rx
            self.weights[ry] = - d + self.weights[x] - self.weights[y]
            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.weights[x] - self.weights[y]

n, m = map(int, input().split())
wuf = WeightedUnionFind(n)
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    if not wuf.same(l, r):
        wuf.unite(l, r, d)
    else:
        if wuf.diff(l, r) != d:
            print("No")
            exit()
print("Yes")

Submission status: Accepted

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

    def find(self, x):
        if self.parent[x] == x:
            return x
        nx = self.find(self.parent[x])
        self.weights[x] += self.weights[self.parent[x]]
        self.parent[x] = nx
        return nx

    def unite(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
            self.weights[rx] = d + self.weights[y] - self.weights[x]
        else:
            self.parent[ry] = rx
            self.weights[ry] = - d + self.weights[x] - self.weights[y]
            if self.rank[rx] == self.rank[ry]:
                # rank等しい時はどちらを親にしても良いが，この場合は統合されたxのrankが1増加することに注意する
                self.rank[rx] += 1

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

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


def main():
    n, m = map(int, input().split())
    wuf = WeightedUnionFind(n)
    for _ in range(m):
        l, r, d = map(int, input().split())
        l -= 1
        r -= 1
        if not wuf.same(l, r):
            wuf.unite(l, r, d)
        else:
            if wuf.diff(l, r) != d:
                print("No")
                exit()
    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def bfs(s):
    q = deque([s])
    visited[s] = True
    
    while q:
        v = q.popleft()
        
        for nv, d in G[v]:
            if visited[nv]:
                if dist[v]+d!=dist[nv]:
                    print('No')
                    exit()
            else:
                visited[nv] = True
                dist[nv] = dist[v]+d
                q.append(nv)

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

for _ in range(M):
    L, R, D = map(int, input().split())
    G[L-1].append((R-1, D))
    G[R-1].append((L-1, -D))
    
visited = [False]*N
dist = [0]*N

for i in range(N):
    if not visited[i]:
        bfs(i)

print('Yes')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
indeg=[0]*n
touch=[0]*n
for _ in range(m):
    l,r,d=map(int,input().split())
    l-=1
    r-=1
    touch[l]=1
    touch[r]=1
    g[l].append((r,d))
    indeg[r]+=1
if m==0:
    print('Yes')
    exit()
entered=False
for i in range(n):
    if indeg[i]==0 and touch[i]==1:
        vis=[False]*n
        entered=True
        dist=[-1]*n
        dist[i]=0
        def dfs(u):
            vis[u]=1
            for v,wt in g[u]:
                if dist[v]==-1:
                    dist[v]=dist[u]+wt
                elif dist[v]!=dist[u]+wt:
                    print('No')
                    exit()
                if vis[v]==False:
                    dfs(v)
        dfs(i)

if entered==False:
    print('No')
else:
    print('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)

n, m = map(int, input().split())
lrd = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n+1)
for l, r, d in lrd:
  if not uf.isSameGroup(l, r):
    uf.Unite(l, r, d)
  else:
    if uf.Diff(l, r) != d:
      print('No')
      exit()

print('Yes')

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**5+1)
def dfs(p):
  for edge in g[p]:
    if x[edge[0]] is not None:
      if x[edge[0]]-x[p]!=edge[1]:
        print('No')
        exit()
    else:
      x[edge[0]]=x[p]+edge[1]
      dfs(edge[0])
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
  u,v,c=map(int,input().split())
  g[u-1].append((v-1,c))
  g[v-1].append((u-1,-c))
x=[None]*n
for i in range(n):
  if x[i]==None:
    x[i]=0
    dfs(i)
print('Yes')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
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]
uf=WeightedUnionFind(n)
for i in range(m):
  l,r,d=map(int,input().split())
  l-=1
  r-=1
  if uf.same(l,r):
    if uf.diff(l,r)!=d:
      print('No')
      exit()
  else:
    uf.union(l,r,d)
print('Yes')

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
L = [deque([]) for _ in range(N)]

for m in range(M):
    l, r, d = [int(x) for x in input().strip().split()]
    L[l-1].append((r, d))
    L[r-1].append((l, -d))

D = [0] * N
F = [False] * N

def dfs(n, d):
    # print('n = {}, d = {}'.format(n, d))
    if F[n-1]:
        if D[n-1] == d:
            # print('  already passed')
            return True
        else:
            # print('  already passed, but wrong')
            return False
    F[n-1] = True
    D[n-1] = d
    for nn, d_ in L[n-1]:
        # print('  dfs({}, {})'.format(nn, d+d_))
        if not dfs(nn, d+d_):
            return False
    else:
        return True

for n in range(1, N+1):
    if not dfs(n, D[n-1]):
        print('No')
        exit()
else:
    print('Yes')

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int, input().split())
edges = [{} for i in range(n+1)]

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

remains = set(range(1,n+1))
deq = deque()

min_ = -1 * 10**10
xs = [min_] * (n+1)

while( len(remains) > 0):
    deq.append( remains.pop() )
    while(len(deq) > 0):
        tmp = deq.popleft()
        if(xs[tmp]  == min_):
            xs[tmp] = 0
        tmp_x = xs[tmp]

        edge = edges[tmp]

        for key,val in edge.items():
            if(xs[key] == min_):
                xs[key] = tmp_x + val
                deq.append( key )
                remains.remove( key )
            else:
                if( xs[key] != tmp_x + val ):
                    print('No')
                    exit()

print('Yes')

Submission status: Accepted

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


class WeightedUnionFind:
    def __init__(self, x):
        self.p = [e for e in range(x)]
        self.rank = [0] * x
        self.weight = [0] * x

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def find_set(self, u):
        if u != self.p[u]:
            v = self.find_set(self.p[u])
            self.weight[u] += self.weight[self.p[u]]
            self.p[u] = v

        return self.p[u]

    def unite(self, u, v, w):
        w += self.weight[u]
        w -= self.weight[v]

        u = self.find_set(u)
        v = self.find_set(v)

        if self.rank[u] < self.rank[v]:
            u, v = v, u
            w = -w

        if self.rank[u] == self.rank[v]:
            self.rank[u] += 1

        self.p[v] = u

        self.weight[v] = w

    def get_weight(self, u):
        self.find_set(u)
        return self.weight[u]

    def diff(self, u, v):
        return self.get_weight(v) - self.get_weight(u)


wuf = WeightedUnionFind(n)

for l, r, d in lrd:
    l -= 1
    r -= 1

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

    else:
        wuf.unite(l, r, d)

print("Yes")