leetcode/leetcode75/day34_947.py at master · wsgggws/leetcode · GitHub

Name: leetcode/leetcode75/day34_947.py at master · wsgggws/leetcode · GitHub
Rating: 4.4 (3419 reviews)
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
fromcollectionsimportdefaultdict
fromtypingimportList


classSolution:
defremoveStones(self, stones: List[List[int]]) ->int:

n=len(stones)
ifn<1:
raiseKeyError
edges=defaultdict(list)
foriinrange(n):
forjinrange(i+1, n):
ifstones[i][0] ==stones[j][0] orstones[i][1] ==stones[j][1]:
edges[i].append(j)
# notes, 是双向图
edges[j].append(i)
visit= [Falsefor_inrange(n)]
connected=0
foriinrange(n):
ifvisit[i] isFalse:
self.bfs(edges, i, visit)
connected+=1
returnn-connected

defbfs(self, edges, start, visit):
queue= [start]
whilequeue:
size=len(queue)
foriinrange(size):
visit[queue[i]] =True
forcityinedges[queue[i]]:
ifvisit[city] isFalse:
queue.append(city)
queue=queue[size:]


if__name__=="__main__":
assertSolution().removeStones(stones=[[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]]) ==5
assertSolution().removeStones(stones=[[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]) ==3
assertSolution().removeStones(stones=[[0, 0]]) ==0
assertSolution().removeStones(stones=[[0, 1], [1, 0], [1, 1]]) ==2