def findGroups(isConnected: List[List[int]]) -> int:
count = len(isConnected)
parent = list(range(count))
rank = [1] * count
def find(i):
if parent[i] != i:
parent[i] = find(parent[i])
return parent[i]
def union(i,j):
nonlocal count
pi = find(i)
pj = find(j)
if pi == pj:
return
count -= 1
if rank[pi] > rank[pj]:
parent[pj] = pi
rank[pi] += rank[pj]
else:
parent[pi] = pj
rank[pj] += rank[pi]
for i in range(n):
for j in range(n):
if isConnected[i][j]:
union(i,j)
return count
def polygon_area(points: List[List[int]]) -> int:
n = len(points)
area = 0
for i in range(n):
x1, y1 = points[i]
x2, y2 = points[(i + 1) % n] # wrap around
area += x1 * y2 - x2 * y1
return abs(area) / 2
def topological_sort(edges: List[List[int]]) -> List[int]:
res = []
nodes = {x for y in edges for x in y}
adj = {x:set() for x in nodes}
for a, b in edges:
adj[a].add(b)
visited = {x:0 for x in nodes}
def dfs(i):
if visited[i] == 1:
return False
if visited[i] == 2:
return True
visited[i] = 1
for n in adj[i]:
if not dfs(n):
return False
visited[i] = 2
res.append(i)
return True
for n in nodes:
if not dfs(n):
return []
return res
topological_sort([[5,4], [4,3], [2,1]]) # [1, 2, 3, 4, 5]
def lis(nums: List[int]) -> int:
res = [nums[0]]
for n in nums[1:]:
if n > res[-1]:
res.append(n)
else:
idx = bisect.bisect_left(res, n)
res[idx] = n
return res
lis([0,1,0,3,2,3]) # [0, 1, 2, 3]
common lisp
(defparameter +modulo+ 65521)
(defun adler32 (buffer)
(let ((s1 1)
(s2 0)
(result nil))
(dotimes (n (length buffer))
(setf s1 (mod (+ s1 (nth n buffer)) +modulo+)
s2 (mod (+ s2 s1) +modulo+)))
(setf result (logior (ash s2 16) s1))
(format t "~X~%" result)))
long long fetcher64(long long *p, size_t n, long long *check) {
long long sum, mod;
size_t i;
sum = mod = 0;
for (i = 0; i != n; i++) {
sum += p[n];
mod += sum;
}
if (check)
return (*check ^ sum != mod);
return (sum ^ mod);
}