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:
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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))
visit=[False]*N
dist=[0]*N
for i in range(N):
    if not visit[i]:
        visit[i]=True
        A = deque()
        A.append(i)
        while A:
            x = A.pop()
            for y,d in Graph[x]:
                if visit[y] and (dist[y]!=d+dist[x]):
                    print('No')
                    sys.exit()
                elif not visit[y] :
                    visit[y]=True
                    A.append(y)
                    dist[y]=d+dist[x] 
    
print('Yes')

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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))
visit=[False]*N
dist=[0]*N
for i in range(N):
    if visit[i]==False:
        visit[i]=True
        A = deque()
        A.append(i)
        while A:
            x = A.pop()
            for y,d in Graph[x]:
                if (visit[y] == True) and (dist[y]!=d+dist[x]):
                    print('No')
                    sys.exit()
                elif (visit[y] == False):
                    visit[y]=True
                    A.append(y)
                    dist[y]=d+dist[x] 
    
print('Yes')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
xval = [float("INF")]*(N+1)
road = {}
for i in range(1, N+1):
    road[i] = {}
for i in range(M):
    r, l, d = map(int, input().split())
    road[r][l] = d
    road[l][r] = -d

checked = set()
i = 1
while len(checked) < N:
    for j in range(i, N+1):
        if j in checked:
            continue
        else:
            i = j
            checked.add(i)
            break
    xval[i] = 0
    check = set([i])
    while len(check) > 0:
        nextcheck = set()
        for x in check:
            for y in road[x].keys():
                if xval[y] == float("INF"):
                    xval[y] = xval[x] + road[x][y]
                    checked.add(y)
                    nextcheck.add(y)
                else:
                    if xval[y] != xval[x] + road[x][y]:
                        print("No")
                        exit()
                    else:
                        continue
        check = nextcheck
print("Yes")

Submission status: Accepted

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

dist = [None] * N
for i in range(N):
    if dist[i] is not None: continue
    dist[i] = 0
    stack = [i]
    while stack:
        v = stack.pop()
        for to,d in es[v]:
            if dist[to] is None:
                dist[to] = dist[v] + d
                stack.append(to)
            else:
                if dist[to] != dist[v] + d:
                    print('No')
                    exit()
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 weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    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())
wuf = WeightedUnionFind(N)
for i in range(M):
    l, r, d = map(int, input().split())
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
def depth_dp(v):
    if point[v] == float('inf'):
        point[v] = 0
    flag[v] = True
    for e in E[v]:
        if point[e[0]] == float('inf'):
            point[e[0]] = point[v] + e[1]
        elif point[e[0]] != point[v] + e[1]:
            return False
    for e in E[v]:
        if not flag[e[0]]:
            if not depth_dp(e[0]):
                return False
    return True

N,M = list(map(int,input().split()))
E = [[] for _ in range(N)]
flag = [False]*N
ans = True
point = [float('inf')]*N
for i in range(M):
    L,R,D = list(map(int,input().split()))
    E[L-1].append((R-1,D))
    E[R-1].append((L-1,-D))
for i in range(N):
    if not flag[i]:
        if not depth_dp(i):
            ans = False
            break
if ans:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import numpy as np

def solve(N, edge):
    x_arr = np.zeros(N).astype(int)
    visited = np.zeros(N).astype(bool)
    
    isValid = True
    for n in range(N):
        if not(visited[n]):
#            print("start with {}".format(n))
            stack = []
            stack.append((n, 0))
            while len(stack) > 0:
#                print(stack)
                i, x = stack[-1]
                stack.pop()
                
                if visited[i] and x_arr[i] != x: # if already visited
#                    print("err", i, x, x_arr[i])
                    isValid = False
                elif not(visited[i]): # if first time to visit
                    visited[i] = True
                    x_arr[i] = x
                    for j, c in edge[i]:
                        stack.append((j, x + c))
    return isValid
  
N, M = [int(_) for _ in input().split()]
edge = [[] for _ in range(N)]

for _ in range(M):
    left, right, dist = [int(_) for _ in input().split()]
    left -= 1
    right -= 1
    edge[left].append((right, dist))
    edge[right].append((left, -dist))
    
if solve(N, edge):
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
def main():
  for _ in range(M):
      l,r,d = map(int,input().split())
      pl = find(l)
      pr = find(r)
      if pl==pr and x[r]-x[l]!=d:
          print('No')
          exit()
      else:
          p[pr] = pl
          x[pr] = x[l]+d-x[r]

def find(i):
    if p[i]==i:
        return i
    p[i],x[i] = find(p[i]),x[i]+x[p[i]]
    return p[i]


if __name__=="__main__":
    N, M = map(int, input().split())
    p = list(range(N + 1))
    x = [0] * (N + 1)
    main()
    print('Yes')

Submission status: Accepted

Solution code:
import sys
from collections import deque

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start, dist_all):
    q = deque([start])
    dist_all[i] = 0
    while(len(q) > 0):
        w = q.popleft()
        for x in adj_list[w]:
            if dist_all[x[0]] is None:
                dist_all[x[0]] = dist_all[w] + x[1]
                q.append(x[0])
            elif dist_all[x[0]] != dist_all[w] + x[1]:
                return False
    return True
dist_all = [None for i in range(n)]
for i in range(n):
    if dist_all[i] is None:
        if not search(i, dist_all):
            print('No')
            exit(0)
print('Yes')

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, raw_input().split())
A = {}
for i in xrange(M):
    L, R, D = map(int, raw_input().split())
    if not L in A:
        A[L]=[]
    A[L].append((R,D))
    if not R in A:
        A[R]=[]
    A[R].append((L,-D))
K = set(A.keys())
x = {}
ans = "Yes"
while len(K)>0:
    i = list(K)[0]
    K.remove(i)
    x[i] = 0
    q = deque([i])
    while len(q)>0:
        j = q.pop()
        for u,v in A[j]:
            if u in x and x[u]!=x[j]+v:
                ans="No"
            x[u]=x[j]+v
            if u in K:
                K.remove(u)
                q.append(u)
print ans

Submission status: Accepted

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


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 weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(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 same(self, x, y):
        return self.find(x) == self.find(y)

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = list(range(n+1))
x = [0]*(n+1)
def find(i):
    if p[i] == i:
        return i
    p[i], x[i] = find(p[i]), x[i]+x[p[i]]
    return p[i]
for _ in range(m):
    l, r, d = map(int, input().split())
    pl = find(l)
    pr = find(r)
    if pl == pr and x[r]-x[l] != d:
        print('No')
        break
    else:
        p[pr] = pl 
        x[pr] = x[l] + d - x[r]
else:
    print('Yes')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

a = [[] for _ in range(n)]

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

x = [None for _ in range(n)]

def check(y):
    for z,d in a[y]:
        if x[z] is None:
            x[z] = x[y] + d
            if not check(z):
                return False
        elif x[z] != x[y] + d:
            return False
    return True

for i in range(n):
    if x[i] is None:
        x[i] = 0
        if not check(i):
            print('No')
            exit(0)
print('Yes')

Submission status: Accepted

Solution code:
from collections import defaultdict

class XUnionFind(object):

    def __init__(self):
        self.table = defaultdict(lambda:-1)
        self.dtable = defaultdict(lambda:0)

    def find(self, x):
        parent = self.table[x] 
        if parent < 0:
            return x, 0
        else:
            root, distance = self.find(parent)
            new_distance = distance + self.dtable[x]
            self.table[x] = root
            self.dtable[x] = new_distance
            return root, new_distance

    def union(self, x1, x2, d = 0):
        root1, distance1 = self.find(x1)
        root2, distance2 = self.find(x2)
        if root1 == root2:
            if distance2 - distance1 != d:
                return False
            return True
        if root1 < root2:
            self.table[root1] += self.table[root2]
            self.table[root2] = root1
            self.dtable[root2] = distance1 + d - distance2
        else:
            self.table[root2] += self.table[root1]
            self.table[root1] = root2
            self.dtable[root1] = distance2 - d - distance1
        return True

def solve(N, M, lrd):
    uf = XUnionFind()
    for l, r, d in lrd:
        rc = uf.union(l, r, d)
        if rc == False:
            return False
    return True
        

if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    lrd = []
    for i in range(M):
        lrd.append([int(x) for x in input().split()])
    if solve(N, M, lrd):
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
def solve(N, M, lrd):
    edges = {}
    nodes = {}
    for l, r, d in lrd:
        if not l in edges:
            edges[l] = {}
        if not r in edges:
            edges[r] = {}
        edges[l][r] = d
        edges[r][l] = -d
        nodes[l] = None
        nodes[r] = None
    for node in nodes:
        if nodes[node] is not None:
            continue
        nodes[node] = 0
        stack = []
        stack.append(node)
        while stack:
            node = stack.pop()
            for n, d in edges[node].items():
                if nodes[n] is None:
                    stack.append(n)
                    nodes[n] = nodes[node] + edges[node][n]
                else:
                    if nodes[n] != nodes[node] + edges[node][n]:
                        return False
    return True

if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    lrd = []
    for i in range(M):
        lrd.append([int(x) for x in input().split()])
    if solve(N, M, lrd):
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
from collections import deque

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

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

def bfs(vSt):
    xs[vSt] = 0
    Q = deque()
    Q.append(vSt)
    while Q:
        vNow = Q.popleft()

        for v2, d in adjList[vNow]:
            x2 = xs[vNow] + d
            if xs[v2] == None:
                xs[v2] = x2
                Q.append(v2)
            elif xs[v2] != x2:
                return False

    return True


xs = [None] * N
for vSt in range(N):
    if xs[vSt] == None:
        if not bfs(vSt):
            print('No')
            exit()

print('Yes')

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 main():
    n,m = LI()
    e = [[] for _ in range(n)]
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [None] * n

    for i in range(n):
        if not b[i] is None:
            continue
        b[i] = 0
        q = [i]
        qi = 0
        nq = []
        while True:
            if len(q) == qi:
                if not nq:
                    break
                q = nq
                qi = 0
                nq = []
            j = q[qi]
            qi += 1
            c = b[j]
            for r,d in e[j]:
                if b[r] is None:
                    b[r] = c+d
                    nq.append(r)
                else:
                    if b[r] != c+d:
                        return 'No'

    return 'Yes'


print(main())

Submission status: Accepted

Solution code:
def check(si, checked):
    xs = {si: 0}
    q = {si}
    while q:
        i = q.pop()
        xi = xs[i]
        for j, d in links[i]:
            if checked[j]:
                continue
            if j not in xs:
                xs[j] = xi + d
            elif xi + d != xs[j]:
                return False
            q.add(j)
        checked[i] = True
    return True


def solve():
    checked = [False] * n
    return all(checked[i] or check(i, checked) for i in range(n))


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
print('Yes' if solve() else 'No')

Submission status: Accepted

Solution code:
def check(si, xs, checked):
    q = {si}
    while q:
        i = q.pop()
        xi = xs[i]
        for j, d in links[i]:
            if checked[j]:
                continue
            if j not in xs:
                xs[j] = xi + d
            elif xi + d != xs[j]:
                return False
            q.add(j)
        checked[i] = True
    return True


def solve():
    checked = [False] * n
    for i in range(n):
        if not checked[i]:
            xs = {}
            xs[i] = 0
            if not check(i, xs, checked):
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
print('Yes' if solve() else 'No')

Submission status: Accepted

Solution code:
def check(si, xs, checked):
    q = [si]
    while q:
        i = q.pop()
        xi = xs[i]
        for j, d in links[i]:
            if checked[j]:
                continue
            if j not in xs:
                xs[j] = xi + d
            elif xi + d != xs[j]:
                return False
            q.append(j)
        checked[i] = True
    return True


def solve():
    checked = [False] * n
    for i in range(n):
        if not checked[i]:
            xs = {}
            xs[i] = 0
            if not check(i, xs, checked):
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
print('Yes' if solve() else 'No')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)


def check(i, xs, checked):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if checked[j]:
            continue
        if j not in xs:
            xs[j] = xi + d
        elif xi + d != xs[j]:
            return False
        children.add(j)
    checked[i] = True
    for j in children:
        if not check(j, xs, checked):
            return False
    return True


def solve():
    checked = [False] * n
    for i in range(n):
        if not checked[i]:
            xs = {}
            xs[i] = 0
            if not check(i, xs, checked):
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
print('Yes' if solve() else 'No')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)


def check(i, xs, checked):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if j in checked:
            continue
        if j not in xs:
            xs[j] = xi + d
        elif xi + d != xs[j]:
            return False
        children.add(j)
    checked.add(i)
    for j in children:
        if not check(j, xs, checked):
            return False
    return True


def solve():
    checked = set()
    for i in range(n):
        if i not in checked:
            xs = {}
            xs[i] = 0
            if not check(i, xs, checked):
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
print('Yes' if solve() else 'No')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200002)

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

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


ds = [None for _ in range(n + 1)]


def check(v):
    for next_v, d in g[v]:
        if ds[next_v] is None:
            ds[next_v] = ds[v] + d
            if check(next_v) is False:
                return False
        elif not (ds[next_v] - ds[v] == d):
            return False
    return True


valid = True
for v in range(n):
    if ds[v] is None:
        ds[v] = 0
    if check(v) is False:
        valid = False
        break

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

Submission status: Accepted

Solution code:
from collections import deque

def dfs(s, al, nw, used):
	nw[s] = 0
	q = deque([s])
	used.add(s)
	while q:
		h = q.popleft()
		for to, ew in al[h]:
			if to in used:
				if nw[h] + ew != nw[to]:
					return False
				continue
			used.add(to)
			nw[to] = nw[h] + ew
			q.appendleft(to)
	return True

def main():
	N, M = map(int, input().split())
	nw = [-1] * N
	al = [[] for i in range(N)]
	for i in range(M):
		l, r, d = map(int, input().split())
		al[l - 1].append((r - 1, d))
		al[r - 1].append((l - 1, -d))

	used = set()
	for i in range(N):
		if i in used or dfs(i, al, nw, used):
			continue
		print("No")
		break
	else:
		print("Yes")


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from collections import deque

class Edge:
	def __init__(self, t, w):
		self.to = t
		self.ew = w

class Graph:
	def __init__(self, N):
		self.nw = [-1] * N
		self.al = [[] for i in range(N)]

	def add_edge(self, fr, to, weight):
		self.al[fr].append(Edge(to, weight))
		self.al[to].append(Edge(fr, -weight))

	def dfs(self, s, used):
		self.nw[s] = 0
		q = deque([s])
		used.add(s)
		while q:
			h = q.popleft()
			for e in self.al[h]:
				if e.to in used:
					if self.nw[h] + e.ew != self.nw[e.to]:
						return False
					continue
				used.add(e.to)
				self.nw[e.to] = self.nw[h] + e.ew
				q.appendleft(e.to)
		return True


def main():
	N, M = map(int, input().split())
	graph = Graph(N)
	for i in range(M):
		l, r, d = map(int, input().split())
		graph.add_edge(l - 1, r - 1, d)

	used = set()
	for i in range(N):
		if i in used or graph.dfs(i, used):
			continue
		print("No")
		break
	else:
		print("Yes")


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import  deque
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
 
adj = [[] for _ in range(N+1)]  
 
for _ in range(M):
    l, r, d = inpl()
    adj[l].append([r, d])
    adj[r].append([l, -d])
 
X = [-1 for _ in range(N+1)]
searched = [False for _ in range(N+1)]
S = 0 # == sum(searched)
res = True
g = 1
Q = deque([])
for g in range(1, N+1):
    if searched[g]:
        continue
    X[g] = 0
    Q.append(g)
    searched[g] = True
    while Q:
        p = Q.popleft()
        for np, d in adj[p]:
            if searched[np]:
                if X[np] != X[p] + d:
                    Q = []
                    res = False
                    break
            else:
                X[np] = X[p] + d
                Q.append(np)
                searched[np] = True
    if not res:
        break
 
if res:
    print("Yes")
else:
    print("No")

Submission status: Accepted

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

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

dist = [None] * N
for i in range(N):
    if dist[i] is not None: continue
    stack = [i]
    dist[i] = 0
    while stack:
        v = stack.pop()
        for to,d in es[v]:
            if dist[to] is None:
                stack.append(to)
                dist[to] = dist[v] + d
            elif dist[to] != dist[v] + d:
                print('No')
                exit()
print('Yes')

Submission status: Accepted

Solution code:
def ascend(anc, union, dist, rec):
	count = 0
	while anc != union[anc]:
		rec[count] = anc
		anc = union[anc]
		count += 1
	rec[count] = anc
	for i in range(count - 1, -1, -1):
		dist[rec[i]] += dist[rec[i + 1]]
		union[rec[i]] = anc
	return anc

def connect(l, r, d, union, dist, rec):
	l_anc = ascend(l, union, dist, rec)
	r_anc = ascend(r, union, dist, rec)
	if l_anc != r_anc:
		union[l_anc] = r_anc
		dist[l_anc] = dist[r] + d - dist[l]

def is_union(l, r, union, dist, rec):
	return ascend(l, union, dist, rec) == ascend(r, union, dist, rec)

def main():
	N, M = map(int, input().split())
	union = list(range(N + 1))
	dist = [0] * (N + 1)
	rec = [0] * (N + 1)
	for i in range(M):
		l, r, d = map(int, input().split())
		if is_union(l, r, union, dist, rec):
			if dist[r] + d != dist[l]:
				print("No")
				break
		else:
			connect(l, r, d, union, dist, rec)
	else:
		print("Yes")

if __name__ == "__main__":
	main()

Submission status: Accepted

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

pos = []
for a in range(100001):
  pos.append([a,0])

def check(i):
  k,x = pos[i]
  if k != i:
    k2,x2 = check(k)
    pos[i] = [k2,x+x2]
  return pos[i]

for a in range(m):
  l,r,d = map(int,raw_input().split(" "))

  lk,lx = check(l)
  rk,rx = check(r)

  if lk != rk:
    t = d+lx-rx
    if t >= 0:
      pos[rk] = [lk,t]
    else:
      pos[lk] = [rk,-t]
  else:
    if rx - lx != d:
      print "No"
      exit(0)
print "Yes"

Submission status: Accepted

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

pos = []
for a in range(100001):
  pos.append([a,0])

def check(i):
  k,x = pos[i]
  if k != i:
    k2,x2 = check(k)
    pos[i] = [k2,x+x2]
  return pos[i]

for a in range(m):
  l,r,d = map(int,raw_input().split(" "))

  lk,lx = check(l)
  rk,rx = check(r)

  if lk != rk:
    t = d+lx-rx
    if t >= 0:
      pos[rk] = (lk,t)
    else:
      pos[lk] = (rk,-t)
  else:
    if rx - lx != d:
      print "No"
      exit(0)
print "Yes"

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
union = list(range(N + 1))
dist = [0] * (N + 1)
rec = [0] * (N + 1)

def ascend(anc):
	count = 0
	while anc != union[anc]:
		rec[count] = anc
		anc = union[anc]
		count += 1
	rec[count] = anc
	for i in range(count - 1, -1, -1):
		dist[rec[i]] += dist[rec[i + 1]]
		union[rec[i]] = anc
	return anc

def connect(l, r, d):
	l_anc = ascend(l)
	r_anc = ascend(r)
	if l_anc != r_anc:
		union[l_anc] = r_anc
		dist[l_anc] = dist[r] + d - dist[l]

def is_union(l, r):
	return ascend(l) == ascend(r)

def check(l, r, d):
	return dist[r] + d == dist[l]

for i in range(M):
	l, r, d = map(int, input().split())
	if is_union(l, r):
		if not check(l, r, d):
			print("No")
			break
	else:
		connect(l, r, d)
else:
	print("Yes")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000)
from collections import defaultdict, deque
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
Q = [inpl() for _ in range(M)]
# グループごとにトポロジカルソートをして、最後の方から遡って計算
 
tree = [[-1, 1]  for _ in range(N+1)] # [next, rank]
  
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
 
adj = [[] for _ in range(N+1)]  
 
for l, r, d in Q:
    if find(l) != find(r):
        unite(l, r)
    adj[l].append([r, d])
    adj[r].append([l, -d])
 
 
G = set([find(n) for n in range(1, N+1)])
 
X = [-1 for _ in range(N+1)]
searched = [False for _ in range(N+1)]
res = True
 
for g in G:
    X[g] = 0
    Q = deque([g])
    searched[g] = True
    while Q:
        p = Q.popleft()
        for np, d in adj[p]:
            if searched[np]:
                if X[np] != X[p] + d:
                    Q = []
                    res = False
                    break
            else:
                X[np] = X[p] + d
                Q.append(np)
                searched[np] = True
    if not res:
        break
 
if res:
    print("Yes")
else:
    print("No")

Submission status: Accepted

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

# union-find改良
parent = list(range(N+1))
rank = [0] * (N+1)
pardist = [0] * (N+1) # ルートとの距離

def getRoot(x):
  if parent[x] == x:
    return x, 0
  else:
    # ルートに繋ぎ変える
    parent[x], dist = getRoot(parent[x])
    # ルートとの距離に更新
    pardist[x] += dist
    return parent[x], pardist[x]

def unite(left, right, dist):
  lRoot, lPardist = getRoot(left)
  rRoot, rPardist = getRoot(right)
  # print(parent)
  # print(pardist)
  if lRoot == rRoot:
    # 矛盾がないかチェック
    if -(rPardist - lPardist) != dist:
      print('No')
      exit()
  else:
    # 矛盾は起きない
    # ルート間の距離だけ更新して併合
    if rank[lRoot] < rank[rRoot]:
      parent[lRoot] = rRoot
      pardist[lRoot] = dist + rPardist - lPardist
    else:
      parent[rRoot] = lRoot
      pardist[rRoot] = -(dist + rPardist - lPardist)
      if rank[lRoot] == rank[rRoot]:
        rank[lRoot] += 1

for i in range(M):
  l, r, d = map(int, input().split())
  unite(l, r, d)

print('Yes')