#2685

Count the Number of Complete Components

pupil · 460 · lc medium +26 · verified · 77.8% accepted · 1,271 likes · top 89%

⚑ DFS / BFS: Connected Components & Reachability

Description

Given an integer n and an undirected graph on vertices 0 to n - 1 described by edges, a connected component is complete when every pair of its nodes is directly connected. Count and return the number of complete connected components.

Example 1:

Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]

Output: 3

Explanation: From the picture above, one can see that all of the components of this graph are complete.

Example 2:

Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]

Output: 1

Explanation: The component containing vertices 0, 1, and 2 is complete since there is an edge between every pair of two vertices. On the other hand, the component containing vertices 3, 4, and 5 is not complete since there is no edge between vertices 4 and 5. Thus, the number of complete components in this graph is 1.

Code

1

2

3

class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:

class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int: