Problem

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.

Examples

Example 1:

graph LR
1 --- 2
3
  
Input:
isConnected = [ [1,1,0],[1,1,0],[0,0,1] ]
Output:
 2

Example 2:

graph TD
1
2
3
  
Input:
isConnected = [ [1,0,0],[0,1,0],[0,0,1] ]
Output:
 3

Solution

Method 1 - DFS

Code

Java
public class Solution {

	public int findCircleNum(int[][] isConnected) {
		boolean[] visited = new boolean[isConnected.length];
		int count = 0;

		for (int i = 0; i < isConnected.length; i++) {
			if (!visited[i]) {
				dfs(isConnected, visited, i);
				count++;
			}
		}

		return count;
	}

	public void dfs(int[][] isConnected, boolean[] visited, int i) {
		for (int j = 0; j < isConnected.length; j++) {
			if (isConnected[i][j] == 1 && !visited[j]) {
				visited[j] = true;
				dfs(isConnected, visited, j);
			}
		}
	}

}

Complexity

  • Time: O(n^2) for doing dfs as it is adjacency matrix representation
  • Space: O(n) for recursion stack and also visited array.

Method 2 - Union Find Data Structure

This is a typical Union Find problem. Just add all the edges to it, and count the number of components.

Code

Java
public class Solution {

	public int findCircleNum(int[][] isConnected) {
		int n = isConnected.length;
		UnionFind uf = new UnionFind(n);

		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				if (isConnected[i][j] == 1) {
					uf.union(i, j);
				}
			}
		}

		return uf.getNumComponents();
	}

	static class UnionFind {

		private int[] parent;

		private int[] rank;

		private int numComponents;

		public UnionFind(int n) {
			this.numComponents = n;
			makeSet();
		}

		private void makeSet() {
			rank = new int[numComponents];
			parent = new int[numComponents];

			for (int i = 0; i < parent.length; i++) {
				parent[i] = i;
				rank[i] = 0;
			}
		}

		public boolean union(int x, int y) {
			int root1 = find(x);
			int root2 = find(y);

			if (root1 == root2) {
				return false;
			}

			if (rank[root1] > rank[root2]) {
				parent[root2] = root1;
			} else {
				parent[root1] = root2;
			}

			if (rank[root1] == rank[root2]) {
				rank[root2] += 1;
			}

			numComponents--;
			return true;
		}

		public int find(int x) {
			while (parent[x] != x) {
				x = parent[x];
			}

			return x;
		}
		// count
		public int getNumComponents() {
			return numComponents;
		}

		public boolean isFullyConnected() {
			return numComponents == 1;
		}
	}
}

Complexity

  • Time: O(NNNXXXNNN)
  • Space: O(NNNXXX)