Algorithm
Problem Name: 547. Number of Provinces
There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
Return the total number of provinces.
Example 1:
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]] Output: 2
Example 2:
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]] Output: 3
Constraints:
1 <= n <= 200n == isConnected.lengthn == isConnected[i].lengthisConnected[i][j]is1or0.isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
vector<int>Tags(M.size());
int tag = 0;
for(int i = 0; i < M.size(); i++){
if(Tags[i]) continue;
Tags[i] = ++tag;
for(int j = 0; j < M[0].size(); j++){
if(j == i || M[i][j] == 0) continue;
if(M[i][j]){
M[i][j] = M[j][i] = 0;
DFS(Tags, M, j, tag);
}
}
}
return tag;
}
void DFS(vector<int>& Tags, vector < vector<int>>& M, int row, int tag){
Tags[row] = tag;
for(int i = 0; i < M[row].size(); i++){
if(M[row][i]){
M[row][i] = M[i][row] = 0;
DFS(Tags, M, i, tag>;
}
}
}
};
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
Map < Integer, Set();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && isConnected[i][j] == 1) {
map.computeIfAbsent(i, k -> new HashSet<>()).add(j);
map.computeIfAbsent(j, k -> new HashSet < >()).add(i);
}
}
}
Set visited = new HashSet<>();
int provinceCount = 0;
for (int i = 0; i < n; i++) {
if (!visited.contains(i)) {
Queue queue = new LinkedList<>();
queue.add(i);
visited.add(i);
while (!queue.isEmpty()) {
int removed = queue.remove();
for (Integer connection : map.getOrDefault(removed, new HashSet < >())) {
if (!visited.contains(connection)) {
queue.add(connection);
visited.add(connection);
}
}
}
provinceCount++;
}
}
return provinceCount;
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const findCircleNum = function(M) {
let count = 0
const visited = {}
const dfs = function(M, i) {
for (let j = 0; j < M[i].length; j++) {
if (M[i][j] == 1 && !visited[j]) {
visited[j] = true
dfs(M, j)
}
}
}
for (let i = 0; i < M.length; i++) {
if (!visited[i]) {
dfs(M, i)
count++
}
}
return count
}
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findCircleNum(self, m):
res, n = 0, len(m)
def explore(i):
m[i][i] = 0
for j in range(n):
if i != j and m[i][j] == m[j][j] == 1: explore(j)
for i in range(n):
if m[i][i] == 1: explore(i); res += 1
return res
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0547_FriendCircles
{
public int FindCircleNum(int[][] M)
{
var N = M.Length;
var uf = new UnionFind(N);
for (int i = 0; i < N; i++)
for (int j = 0; j < i; j++)
if (M[i][j] == 1)
uf.Union(i, j);
return uf.Count;
}
public class UnionFind
{
private int[] parents;
public UnionFind(int N)
{
parents = new int[N];
for (int i = 0; i < N; i++)
parents[i] = i;
Count = N;
}
public int Count { get; set; }
public int Find(int i)
{
if (parents[i] != i)
parents[i] = Find(parents[i]);
return parents[i];
}
public void Union(int i, int j)
{
var index1 = Find(i);
var index2 = Find(j);
if (index1 == index2) return;
parents[index1] = index2;
Count--;
}
}
}
}
Input
Output