Number of Provinces

Medium

There are n cities. You are given an n x n matrix grid where grid[i][j] = 1 means city i and city j are directly connected. A province is a group of directly or indirectly connected cities. Return the total number of provinces.

Example 1

Input:  grid = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Example 2

Input:  grid = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Constraints

• 1 <= n <= 200
• grid[i][j] is 1 or 0
• grid[i][i] == 1
• grid[i][j] == grid[j][i].