Given an undirected graph with V vertices. We say two vertices u and v belong to a single province if there is a path from u to v or v to u. Your task is to find the number of provinces.
Note:  A province is a group of directly or indirectly connected cities and no other cities outside of the group. 
Example 1:
Input:
[
 [1, 0, 1],
 [0, 1, 0],
 [1, 0, 1]
]
Output:
2
Explanation:
The graph clearly has 2 Provinces [1,3] and [2]. As city 1 and city 3 has a path between them they belong to a single province. City 2 has no path to city 1 or city 3 hence it belongs to another province.
Example 2:
Input:
[
 [1, 1],
 [1, 1]
]
Output :
1
Your Task:  
You don't need to read input or print anything. Your task is to complete the function numProvinces() which takes an integer V and an adjacency matrix adj as input and returns the number of provinces. adj[i][j] = 1, if nodes i and j are connected and adj[i][j] = 0, if not connected.
Expected Time Complexity: O(V^{2})
Expected Auxiliary Space: O(V)
Constraints:
1 ≤ V ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



class Solution:

    def numProvinces(self, adj, V):

        # code here 

Solutions:
def make_adj(mat, adj):
	for i in range(len(mat)):
		for j in range(len(mat[0])):
			if mat[i][j] == 1 and i != j:
				adj[i].append(j)
	return adj

def dfs(adj, s, visited):
	visited[s] = True
	for u in adj[s]:
		if visited[u] == False:
			dfs(adj, u, visited)

def dfs_connected(adj):
	visited = [False] * len(adj)
	count = 0
	for u in range(len(adj)):
		if visited[u] == False:
			count += 1
			dfs(adj, u, visited)
	return count

class Solution:

	def numProvinces(self, adj, V):
		adj_edges = [[] for i in range(V)]
		adj = make_adj(adj, adj_edges)
		return dfs_connected(adj)


class Solution:

	def numProvinces(self, adj, V):
		from collections import defaultdict
		visit = set()
		adjlist = defaultdict(list)
		for i in range(V):
			for j in range(V):
				if adj[i][j] == 1:
					adjlist[i].append(j)
					adjlist[j].append(i)

		def dfs(node):
			if node in visit:
				return
			visit.add(node)
			for neig in adjlist[node]:
				if neig not in visit:
					dfs(neig)
		res = 0
		for i in range(V):
			if i not in visit:
				res += 1
				dfs(i)
		return res


from queue import Queue

class Solution:

	def bfsTraversal(self, i, adj, visited):
		visited[i] = True
		q = Queue()
		q.put(i)
		while not q.empty():
			p = q.get()
			for j in range(V):
				if not visited[j + 1] and adj[p - 1][j] == 1:
					visited[j + 1] = True
					q.put(j + 1)

	def numProvinces(self, adj, V):
		visited = [False] * (V + 1)
		n = 0
		for i in range(1, V + 1):
			if not visited[i]:
				n += 1
				self.bfsTraversal(i, adj, visited)
		return n


import collections

class Solution:

	def numProvinces(self, isConnected, V):
		provinces = 0
		visited = set()

		def dfs(city):
			q = collections.deque()
			q.append(city)
			while q:
				cur_city = q.popleft()
				for (i, connected) in enumerate(isConnected[cur_city]):
					if connected and i not in visited:
						q.append(i)
						visited.add(i)
		for i in range(len(isConnected)):
			if i not in visited:
				dfs(i)
				provinces += 1
		return provinces


class Solution:

	def findparent(self, node, parent):
		if parent[node] == node:
			return node
		parent[node] = self.findparent(parent[node], parent)
		return parent[node]

	def unite(self, a, b, parent):
		m = self.findparent(a, parent)
		n = self.findparent(b, parent)
		parent[max(m, n)] = min(m, n)

	def numProvinces(self, adj, V):
		queue = []
		parent = [i for i in range(V)]
		for i in range(V):
			for j in range(V):
				if adj[i][j] == 1 and i != j:
					queue.append([i, j])
		while len(queue):
			(a, b) = queue.pop()
			if self.findparent(a, parent) == self.findparent(b, parent):
				continue
			self.unite(a, b, parent)
		count = 0
		for i in range(V):
			if i == parent[i]:
				count += 1
		return count


from collections import defaultdict

def dfs(node, visisted, AdjList):
	visisted.add(node)
	for adjNode in AdjList[node]:
		if adjNode not in visisted and adjNode != node:
			dfs(adjNode, visisted, AdjList)

class Solution:

	def numProvinces(self, adj, V):
		AdjList = defaultdict(list)
		ROW = len(adj)
		COL = len(adj[0])
		for r in range(ROW):
			for c in range(COL):
				if adj[r][c] == 1:
					AdjList[r].append(c)
		visisted = set()
		count = 0
		for node in range(V):
			if node not in visisted:
				count += 1
				dfs(node, visisted, AdjList)
		return count


class Solution:

	def numProvinces(self, adj, V):
		visited = [0] * V
		cnt = 0
		for i in range(V):
			if not visited[i]:
				cnt += 1
				self.dfs(i, visited, adj, cnt)
		return cnt

	def dfs(self, node, visited, adj, cnt):
		visited[node] = 1
		for i in range(len(adj)):
			if adj[node][i] == 1 and (not visited[i]):
				self.dfs(i, visited, adj, cnt)


class Solution:

	def bfs(self, adj, V, vertex, visited):
		queue = []
		queue.append(vertex)
		visited[vertex] = True
		while queue:
			node = queue.pop(0)
			for i in adj[node]:
				if visited[i] == False:
					queue.append(i)
					visited[i] = True

	def numProvinces(self, adj, V):
		adjlist = [[] for i in range(V + 1)]
		for i in range(V):
			for j in range(V):
				if adj[i][j] == 1 and i != j:
					adjlist[i].append(j)
					adjlist[j].append(i)
		vis = [False for i in range(V)]
		cnt = 0
		for i in range(V):
			if vis[i] == False:
				self.bfs(adjlist, V, i, vis)
				cnt += 1
		return cnt


def dfs(adj, i, vis):
	vis.add(i)
	for j in adj[i]:
		if j not in vis:
			dfs(adj, j, vis)

class Solution:

	def numProvinces(self, adj, V):
		vis = set()
		ans = 0
		mp = {}
		for i in range(V):
			mp[i] = []
		for i in range(V):
			for j in range(V):
				if adj[i][j] == 1:
					mp[i].append(j)
					mp[j].append(i)
		for i in range(V):
			if i not in vis:
				ans += 1
				dfs(mp, i, vis)
		return ans


class Solution:

	def numProvinces(self, adj, V):
		provinces = 0
		visited = dict()
		for i in range(V):
			if i not in visited:
				q = [i]
				visited[i] = True
				while q:
					node = q.pop(0)
					for j in range(V):
						if adj[node][j] == 1 and j not in visited:
							q.append(j)
							visited[j] = True
				provinces += 1
		return provinces


from collections import defaultdict

class Solution:

	def numProvinces(self, adj, V):
		path = defaultdict(list)
		visited = set()
		m = len(adj)
		n = len(adj[0])
		for i in range(m):
			for j in range(n):
				if i != j and adj[i][j] == 1:
					path[i].append(j)
					path[j].append(i)

		def dfs(node):
			if node not in visited:
				visited.add(node)
				for i in path[node]:
					if i not in visited:
						dfs(i)
		count = 0
		for i in range(V):
			if i not in visited:
				count += 1
				dfs(i)
		return count


class Solution:

	def dfs(self, x, adj, vis):
		vis[x] += 1
		for i in range(len(adj)):
			if adj[x][i] == 1:
				if vis[i] == 0:
					self.dfs(i, adj, vis)

	def numProvinces(self, adj, V):
		ans = 0
		vis = [0] * V
		for i in range(V):
			if vis[i] == 0:
				self.dfs(i, adj, vis)
				ans += 1
		return ans


class Solution:

	def numProvinces(self, adj, V):

		class UnionFind:

			def __init__(self, size):
				self.root = {i: i for i in range(size)}
				self.rank = [0] * size
				self.size = size

			def find(self, member):
				root = member
				while root != self.root[root]:
					root = self.root[root]
				while member != root:
					parent = self.root[member]
					self.root[member] = root
					member = parent
				return root

			def union(self, x, y):
				rootX = self.find(x)
				rootY = self.find(y)
				if rootX != rootY:
					if self.rank[rootX] > self.rank[rootY]:
						self.root[rootY] = rootX
					elif self.rank[rootX] < self.rank[rootY]:
						self.root[rootX] = rootY
					else:
						self.root[rootY] = rootX
						self.rank[rootX] += 1

			def connected(self, x, y):
				return self.root[x] == self.root[y]
		check = UnionFind(V)
		for i in range(V):
			for j in range(V):
				if adj[i][j]:
					check.union(i, j)
		parent = 0
		for i in range(V):
			if check.root[i] == i:
				parent += 1
		return parent


class Solution:

	def numProvinces(self, adj, V):
		provinces = 0
		visited = [False] * V
		res = []
		for node in range(V):
			if not visited[node]:
				provinces += 1
				queue = [node]
				visited[node] = True
				while queue:
					node = queue.pop(0)
					for i in range(V):
						if adj[node][i] == 1 and (not visited[i]):
							queue.append(i)
							visited[i] = True
		return provinces


class Solution:

	def numProvinces(self, adj, V):
		if V == 0:
			return 0
		visited = [0 for i in range(V)]
		count = 0
		for i in range(V):
			if visited[i] == 0:
				count = count + 1
				self.dfs(i, -1, visited, adj, V)
		return count

	def dfs(self, node, prev, visited, adj, V):
		visited[node] = 1
		for i in range(V):
			if visited[i] == 0 and i != prev and adj[node][i]:
				self.dfs(i, node, visited, adj, V)


class Solution:

	def numProvinces(self, adj, V):

		def dfs(adj, i):
			adj[i][i] = 0
			for j in range(len(adj)):
				if adj[i][j] == 1:
					adj[i][j] = 0
					if adj[j][j] == 1:
						dfs(adj, j)
		ans = 0
		for i in range(V):
			if adj[i][i] == 0:
				continue
			ans += 1
			dfs(adj, i)
		return ans


class Solution:

	def numProvinces(self, adj, V):

		def bfs(adjlst, node, visited, q):
			visited[node] = 1
			q.append(node)
			while q:
				f = q[0]
				q.pop(0)
				for i in adjlst[f]:
					if visited[i] != 1:
						visited[i] = 1
						q.append(i)
		visited = [0] * V
		q = []
		c = 0
		adjlst = [[] for i in range(V)]
		for i in range(V):
			for j in range(V):
				if adj[i][j] == 1 and i != j:
					adjlst[i].append(j)
					adjlst[j].append(i)
		for i in range(V):
			if visited[i] != 1:
				c += 1
				bfs(adjlst, i, visited, q)
		return c


class Solution:

	def numProvinces(self, adj, V):

		def dfs(adjlst, node, visited):
			visited[node] = 1
			for i in adjlst[node]:
				if visited[i] != 1:
					dfs(adjlst, i, visited)
		visited = [0] * V
		q = []
		c = 0
		adjlst = [[] for i in range(V)]
		for i in range(V):
			for j in range(V):
				if adj[i][j] == 1 and i != j:
					adjlst[i].append(j)
					adjlst[j].append(i)
		for i in range(V):
			if visited[i] != 1:
				c += 1
				dfs(adjlst, i, visited)
		return c


class Solution:

	def numProvinces(self, adj, V):
		n = len(adj)
		visited = [0 for _ in range(n)]

		def dfs(i):
			visited[i] = 1
			for city in range(n):
				if not visited[city] and adj[i][city]:
					dfs(city)
			return
		count = 0
		for i in range(0, n):
			if not visited[i]:
				dfs(i)
				count += 1
		return count


from queue import Queue

class Solution:

	def bfsTraversal(self, adj, stNode, isVisited, V):
		q = Queue()
		q.put(stNode)
		isVisited[stNode] = 1
		while q.qsize() > 0:
			topNode = q.get()
			for adjNode in range(V):
				if not isVisited[adjNode + 1] and adj[topNode - 1][adjNode]:
					q.put(adjNode + 1)
					isVisited[adjNode + 1] = 1

	def numProvinces(self, adj, V):
		isVisited = [0 for _ in range(V + 1)]
		res = 0
		for i in range(1, V + 1):
			if not isVisited[i]:
				res += 1
				self.bfsTraversal(adj, i, isVisited, V)
		return res


from collections import defaultdict

class Solution:

	def numProvinces(self, adj, V):
		adjList = defaultdict(list)
		for row in range(V):
			for col in range(V):
				if adj[row][col] == 1 and row != col:
					adjList[row].append(col)
					adjList[col].append(row)
		visted = set()

		def dfs(node):
			visted.add(node)
			for i in adjList[node]:
				if i not in visted:
					dfs(i)
		noOfProvince = 0
		for node in range(V):
			if node not in visted:
				noOfProvince += 1
				dfs(node)
		return noOfProvince


from collections import defaultdict, deque

class Solution:

	def numProvinces(self, adj, V):
		q = deque()
		visited = set()
		count = 0
		for node in range(V):
			if node in visited:
				continue
			q.append(node)
			while q:
				front = q.popleft()
				if front in visited:
					continue
				visited.add(front)
				for i in range(len(adj[front])):
					if i == front or adj[front][i] == 0:
						continue
					q.append(i)
			count += 1
		return count


class Solution:

	def numProvinces(self, adj, V):

		def bfs(V, adjLS):
			final = []
			queue = []
			queue.append(V)
			while len(queue) > 0:
				element = queue.pop(0)
				final.append(element)
				for i in adjLs[element]:
					if i == -1:
						continue
					if visited[i] == False:
						queue.append(i)
						visited[i] = True
		visited = [False] * V
		adjLs = [[-1] for i in range(V)]
		c = 0
		for i in range(0, V):
			for j in range(0, V):
				if adj[i][j] == 1 and i != j:
					adjLs[i].append(j)
		for i in range(0, V):
			if visited[i] == False:
				visited[i] = True
				c = c + 1
				bfs(i, adjLs)
		return c


from collections import *

class Solution:

	def numProvinces(self, adj, V):
		adj_list = defaultdict(list)
		for i in range(V):
			for j in range(V):
				if adj[i][j] == 1 and i != j:
					adj_list[i].append(j)
		visit = [False] * V

		def dfs(visit, s):
			visit[s] = True
			for j in adj_list[s]:
				if not visit[j]:
					dfs(visit, j)
		count = 0
		for i in range(V):
			if not visit[i]:
				count += 1
				dfs(visit, i)
		return count


class Solution:

	def numProvinces(self, adj, V):
		n = len(adj)
		visited = [0] * n
		adjj = [[] for i in range(V)]
		for i in range(0, n):
			for j in range(0, n):
				if adj[i][j] == 1 and i != j:
					adjj[i].append(j)
					adjj[j].append(i)
		count = 0
		for i in range(0, n):
			if visited[i] == 0:
				count += 1
				self.dfs(i, visited, adjj)
		return count

	def dfs(self, node, visited, adjj):
		visited[node] = 1
		for neigh in adjj[node]:
			if visited[neigh] == 0:
				self.dfs(neigh, visited, adjj)


class Solution:

	def numProvinces(self, adj, V):
		lis = adj
		d = {}
		count = 0
		l = [-1] * V
		for i in range(0, V):
			d[i] = []
			for j in range(0, V):
				if i != j and adj[i][j] == 1:
					d[i].append(j)

		def fun(starting, l):
			l[starting] = 1
			for j in d[starting]:
				if l[j] != 1:
					fun(j, l)
			return
		for i in range(0, len(l)):
			if l[i] != 1:
				count = count + 1
				fun(i, l)
		return count


class Solution:

	def numProvinces(self, adj, V):
		visited = [0 for i in range(V)]
		ans = 0

		def traverse(i):
			if visited[i] == 0:
				visited[i] = 1
				for j in range(V):
					if adj[i][j] == 1 and i != j and (visited[j] == 0):
						traverse(j)
		for i in range(V):
			if visited[i] == 0:
				ans += 1
				visited[i] = 1
				for j in range(V):
					if adj[i][j] == 1 and i != j and (visited[j] == 0):
						traverse(j)
		return ans