[hero planet July training leetcode problem solving daily] 17th kuansou

daily

There is only one question today .

subject

One 、2316. Count the logarithm of points that cannot reach each other in an undirected graph

link : 2316. Count the logarithm of points that cannot reach each other in an undirected graph

1. Title Description

2. Thought analysis

• I did it during the weekly match , At that time, we used parallel search .
• Today, we need a wide search , To learn .
• 

3. Code implementation

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        for u,v in edges:
            g[u].append(v)
            g[v].append(u)
        visited = [0] * n
        def bfs(u):
            q = deque([u])
            visited[u] = 1
            s = 0
            while q :
                u = q.popleft()
                s += 1
                for v in g[u]:
                    if visited[v] == 0:
                        q.append(v)
                        visited[v] = 1
            return s 
        ans = 0
        for i in range(n):            
            if visited[i] == 0:
                s = bfs(i)
                # print(i,s)
                ans += s*(n-s)
        return ans//2