Submission #38284930

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import defaultdict
from itertools import chain
class DSU():
    def __init__(self, n=None):
        self.dsu = defaultdict(lambda: -1)
        if n: 
            for i in range(n): self.dsu[i]
    
    def leader(self, i):
        if self.dsu[i] < 0: return i
        self.dsu[i] = self.leader(self.dsu[i])
        return self.dsu[i]
    def merge(self, i, j):
        '''サイズの大きい方(x)に小さい方(y)をマージ'''
        if i == j: return
        x = self.leader(i)
        y = self.leader(j)
        if x == y: return
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import defaultdict
from itertools import chain


class DSU():
    def __init__(self, n=None):
        self.dsu = defaultdict(lambda: -1)
        if n: 
            for i in range(n): self.dsu[i]
    
    def leader(self, i):
        if self.dsu[i] < 0: return i
        self.dsu[i] = self.leader(self.dsu[i])
        return self.dsu[i]

    def merge(self, i, j):
        '''サイズの大きい方(x)に小さい方(y)をマージ'''
        if i == j: return
        x = self.leader(i)
        y = self.leader(j)
        if x == y: return

        if self.dsu[x] > self.dsu[y]: x, y = y, x

        self.dsu[x] += self.dsu[y]
        self.dsu[y] = x
    
    def members(self, i):
        l = self.leader(i)
        return [k for k, v in self.dsu.items() if self.leader(k) == l]
    
    def __len__(self):
        return len([1 for v in self.dsu.values() if v < 0])
      


def D(N, ST):
    mapper = {name: i for i, name in enumerate(set(chain.from_iterable(ST)))}
    
    dsu = DSU()
    for s, t in ST:
        if dsu.leader(mapper[s]) == dsu.leader(mapper[t]):
            return "No"
        dsu.merge(mapper[s], mapper[t])

    return "Yes"

N = int(input())
ST = [input().split() for _ in range(N)]

print(D(N, ST))

Submission Info

Judge Result