✅[Python] Simple and Clean, beats 99.95%✅
Please upvote if you find this helpful. \u270C\n\n\nThis is an NFT\n\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem c
### Please upvote if you find this helpful. \u270C\n<img src="https://assets.leetcode.com/users/images/b8e25620-d320-420a-ae09-94c7453bd033_1678818986.7001078.jpeg" alt="Cute Robot - Stable diffusion" width="200"/>\n\n*This is an NFT*\n\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem can be thought of as finding the number of connected components in an undirected graph. Each city represents a node in the graph and an edge exists between two nodes if the cities are directly connected. A province is equivalent to a connected component in the graph.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialize a disjoint set data structure with each city as a separate set.\n1. Iterate over the adjacency matrix and for each pair of cities that are directly connected, merge their sets using the `union` operation.\n1. The number of provinces is equal to the number of disjoint sets at the end.\n\nThe code uses a disjoint set data structure with path compression and `union` by rank to keep track of the connected components. The `find` function finds the representative element of the set containing `x` and the `union` function merges two sets if their representative elements are different.\n# Complexity\n- Time complexity: $$O(n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def findCircleNum(self, AMat: List[List[int]]) -> int:\n        n = len(AMat)\n        parent = [i for i in range(n)]\n        rank = [1]*(n)\n        # find function with path compression\n        def find(x):\n            p = parent[x]\n            while p!=parent[p]:\n                parent[p] = parent[parent[p]]\n                p = parent[p]\n            parent[x] = p\n            return p\n\n        # union function with union by rank\n        def union(x1,x2):\n            p1, p2 = find(x1), find(x2)\n            if p1==p2:\n                return False\n            if rank[p1]>=rank[p2]:\n                rank[p1]+=rank[p2]\n                parent[p2] = p1\n            else:\n                rank[p2]+=rank[p1]\n                parent[p1] = p2\n            return True\n        # iterate over adjacency matrix and merge sets\n        for i in range(n):\n            for j in range(i+1, n):\n                if AMat[i][j] == 1:\n                    union(i, j)\n        # count number of disjoint sets\n        provinces = [find(x) for x in parent]\n        return len(set(provinces))\n\n```
['Depth-First Search', 'Breadth-First Search', 'Union Find', 'Graph', 'Python3']