-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathceiling.py
51 lines (42 loc) · 1.2 KB
/
ceiling.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Node(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class Tree(object):
def __init__(self):
self.root = None
self.num_nodes = 0
def addNode(self, val):
self.root = self._addNode(self.root, val)
self.num_nodes += 1
def _addNode(self, node, val):
if node is None:
return Node(val)
elif val < node.val:
node.left = self._addNode(node.left, val)
else:
node.right = self._addNode(node.right, val)
return node
def hash(self):
if self.root is None:
return "S"
return self._hash(self.root)
def _hash(self, node):
hash_str = ""
if node.right is not None:
hash_str += "R" + self._hash(node.right)
if node.left is not None:
hash_str += "L" + self._hash(node.left)
return hash_str + "S"
def main():
t, n = map(int, input().split())
seen = set()
for _ in range(t):
bst = Tree()
for val in map(int, input().split()):
bst.addNode(val)
seen.add(bst.hash())
print (len(seen))
if __name__ == '__main__':
main()