<p>You are given an integer <code>n</code>. There is an <strong>undirected</strong> graph with <code>n</code> vertices, numbered from <code>0</code> to <code>n - 1</code>. You are given a 2D integer array <code>edges</code> where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> denotes that there exists an <strong>undirected</strong> edge connecting vertices <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code>.</p>

<p>Return <em>the number of <strong>complete connected components</strong> of the graph</em>.</p>

<p>A <strong>connected component</strong> is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.</p>

<p>A connected component is said to be <b>complete</b> if there exists an edge between every pair of its vertices.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2023/04/11/screenshot-from-2023-04-11-23-31-23.png" style="width: 671px; height: 270px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> From the picture above, one can see that all of the components of this graph are complete.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2023/04/11/screenshot-from-2023-04-11-23-32-00.png" style="width: 671px; height: 270px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 50</code></li>
	<li><code>0 &lt;= edges.length &lt;= n * (n - 1) / 2</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li>There are no repeated edges.</li>
</ul>

class UnionFind:
    def __init__(self, n):
        # each node has itself as root
        self.rank = [1 for i in range(n)]
        self.parents = [i for i in range(n)]

    # find the parent of x
    # path compression: 
    #  - set the parent of x to the parent of the parent?
    #  - or compute the root and then set it for all nodes
    def find(self, x):
        if x != self.parents[x]:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        # find the root of x and y
        root_x = self.find(x)
        root_y = self.find(y)
        rank_x = self.rank[root_x]
        rank_y = self.rank[root_y]

        # elements are in the same set
        if root_x == root_y:
            return

        if rank_x < rank_y:
            self.parents[root_x] = root_y
        elif rank_y < rank_x:
            self.parents[root_y] = root_x
        else:
            self.parents[root_x] = root_y
            self.rank[root_y] += 1

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

        graph = defaultdict(set)

        # UF to find the connected components
        for (x, y) in edges:
            uf.union(x, y)
            graph[x].add(y)
            graph[y].add(x)

        # then for each CC, check if it's complete
        ccs = defaultdict(set)
        for i in range(n):
            root = uf.find(i)
            ccs[root].add(i)

        #print(uf.parents)
        #print(uf.rank)
        total = 0
        for root, cc in ccs.items():
            is_complete = True
            for start in cc:
                # print(start, cc, graph[start])
                if len(graph[start]) != len(cc) - 1:
                    is_complete = False
                    break
                if graph[start] | cc != cc:
                    is_complete = False
                    break
                if graph[start] & cc != graph[start]:
                    is_complete = False
                    break
            # print(cc)
            if is_complete:
                total += 1


        return total
        

581