123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Function for BFS traversal
void bfs(int node, vector<int> adjLs[], int vis[]) {
// Mark the node as visited
vis[node] = 1;
// Queue required for BFS traversal
queue <int> q;
// To start traversal from node
q.push(node);
/* Keep on traversing till
the queue is not empty */
while(!q.empty()) {
// Get the node
int i = q.front();
q.pop();
// Traverse its unvisited neighbours
for(auto adjNodes: adjLs[i]) {
if(vis[adjNodes] != 1) {
// Mark the node as visited
vis[adjNodes] = 1;
// Add the node to queue
q.push(adjNodes);
}
}
}
}
// Function for DFS traversal
void dfs(int node, vector<int> adjLs[], int vis[]) {
// Mark the node as visited
vis[node] = 1;
// Traverse its unvisited neighbours
for(auto it: adjLs[node]) {
if(!vis[it]) {
// Recursively perform DFS
dfs(it, adjLs, vis);
}
}
}
public:
/* Function to find the number of
provinces in the given graph */
int numProvinces(vector<vector<int>> adj) {
// Variable to store number of nodes
int V = adj.size();
// To store adjacency list
vector<int> adjLs[V];
// Convert adjacency matrix to adjacency list
for(int i=0; i < V; i++) {
for(int j=0; j < V; j++) {
// self nodes are not considered
if(adj[i][j] == 1 && i != j) {
adjLs[i].push_back(j);
adjLs[j].push_back(i);
}
}
}
// Visited array
int vis[V] = {0};
// Variable to store number of provinces
int cnt = 0;
// Start Traversal
for(int i=0; i < V; i++) {
// If the node is not visited
if(!vis[i]) {
// Increment counter
cnt++;
// Start traversal from current node
bfs(i, adjLs, vis);
//dfs(i, adjLs, vis);
}
}
// Return the count
return cnt;
}
};
int main() {
vector<vector<int>> adj =
{
{1, 0, 0, 1},
{0, 1, 1, 0},
{0, 1, 1, 0},
{1, 0, 0, 1}
};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to find the
provinces in the given graph */
int ans = sol.numProvinces(adj);
cout << "The number of provinces in the given graph is: " << ans;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119
import java.util.*;
class Solution {
// Function for BFS traversal
private void bfs(int node, List<Integer> adjLs[], boolean[] vis) {
// Mark the node as visited
vis[node] = true;
// Queue required for BFS traversal
Queue<Integer> q = new LinkedList<>();
// To start traversal from node
q.add(node);
/* Keep on traversing till
the queue is not empty */
while (!q.isEmpty()) {
// Get the node
int i = q.poll();
// Traverse its unvisited neighbours
for (int adjNodes : adjLs[i]) {
if (!vis[adjNodes]) {
// Mark the node as visited
vis[adjNodes] = true;
// Add the node to queue
q.add(adjNodes);
}
}
}
}
// Function for DFS traversal
private void dfs(int node, List<Integer> adjLs[], boolean[] vis) {
// Mark the node as visited
vis[node] = true;
// Traverse its unvisited neighbours
for (int it : adjLs[node]) {
if (!vis[it]) {
// Recursively perform DFS
dfs(it, adjLs, vis);
}
}
}
/* Function to find the number of
provinces in the given graph */
public int numProvinces(int[][] adj) {
// Variable to store number of nodes
int V = adj.length;
// To store adjacency list
List<Integer>[] adjLs = new ArrayList[V];
for (int i = 0; i < V; i++) {
adjLs[i] = new ArrayList<>();
}
// Convert adjacency matrix to adjacency list
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
// self nodes are not considered
if (adj[i][j] == 1 && i != j) {
adjLs[i].add(j);
adjLs[j].add(i);
}
}
}
// Visited array
boolean[] vis = new boolean[V];
// Variable to store number of provinces
int cnt = 0;
// Start Traversal
for (int i = 0; i < V; i++) {
// If the node is not visited
if (!vis[i]) {
// Increment counter
cnt++;
// Start traversal from current node
bfs(i, adjLs, vis);
//dfs(i, adjLs, vis);
}
}
// Return the count
return cnt;
}
public static void main(String[] args) {
int[][] adj = {
{1, 0, 0, 1},
{0, 1, 1, 0},
{0, 1, 1, 0},
{1, 0, 0, 1}
};
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to find the
provinces in the given graph */
int ans = sol.numProvinces(adj);
System.out.println("The number of provinces in the given graph is: " + ans);
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
from collections import deque
class Solution:
# Function for BFS traversal
def bfs(self, node, adjLs, vis):
# Mark the node as visited
vis[node] = 1
# Queue required for BFS traversal
q = deque()
# To start traversal from node
q.append(node)
# Keep on traversing till
# the queue is not empty
while q:
# Get the node
i = q.popleft()
# Traverse its unvisited neighbours
for adjNodes in adjLs[i]:
if vis[adjNodes] != 1:
# Mark the node as visited
vis[adjNodes] = 1
# Add the node to queue
q.append(adjNodes)
# Function for DFS traversal
def dfs(self, node, adjLs, vis):
# Mark the node as visited
vis[node] = 1
# Traverse its unvisited neighbours
for it in adjLs[node]:
if not vis[it]:
# Recursively perform DFS
self.dfs(it, adjLs, vis)
# Function to find the number of
# provinces in the given graph
def numProvinces(self, adj):
# Variable to store number of nodes
V = len(adj)
# To store adjacency list
adjLs = [[] for _ in range(V)]
# Convert adjacency matrix to adjacency list
for i in range(V):
for j in range(V):
# self nodes are not considered
if adj[i][j] == 1 and i != j:
adjLs[i].append(j)
adjLs[j].append(i)
# Visited array
vis = [0] * V
# Variable to store number of provinces
cnt = 0
# Start Traversal
for i in range(V):
# If the node is not visited
if not vis[i]:
# Increment counter
cnt += 1
# Start traversal from current node
self.bfs(i, adjLs, vis)
#self.dfs(i, adjLs, vis)
# Return the count
return cnt
# Main function to test the solution
if __name__ == "__main__":
adj = [
[1, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[1, 0, 0, 1]
]
# Creating an instance of Solution class
sol = Solution()
# Function call to find the provinces in the given graph
ans = sol.numProvinces(adj)
print("The number of provinces in the given graph is:", ans)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111
class Solution {
// Function for BFS traversal
bfs(node, adjLs, vis) {
// Mark the node as visited
vis[node] = 1;
// Queue required for BFS traversal
let q = [];
// To start traversal from node
q.push(node);
// Keep on traversing till
// the queue is not empty
while (q.length !== 0) {
// Get the node
let i = q.shift();
// Traverse its unvisited neighbours
for (let adjNodes of adjLs[i]) {
if (vis[adjNodes] !== 1) {
// Mark the node as visited
vis[adjNodes] = 1;
// Add the node to queue
q.push(adjNodes);
}
}
}
}
// Function for DFS traversal
dfs(node, adjLs, vis) {
// Mark the node as visited
vis[node] = 1;
// Traverse its unvisited neighbours
for (let it of adjLs[node]) {
if (!vis[it]) {
// Recursively perform DFS
this.dfs(it, adjLs, vis);
}
}
}
// Function to find the number of
// provinces in the given graph
numProvinces(adj) {
// Variable to store number of nodes
let V = adj.length;
// To store adjacency list
let adjLs = new Array(V).fill().map(() => []);
// Convert adjacency matrix to adjacency list
for (let i = 0; i < V; i++) {
for (let j = 0; j < V; j++) {
// self nodes are not considered
if (adj[i][j] === 1 && i !== j) {
adjLs[i].push(j);
adjLs[j].push(i);
}
}
}
// Visited array
let vis = new Array(V).fill(0);
// Variable to store number of provinces
let cnt = 0;
// Start Traversal
for (let i = 0; i < V; i++) {
// If the node is not visited
if (!vis[i]) {
// Increment counter
cnt++;
// Start traversal from current node
this.bfs(i, adjLs, vis);
//this.dfs(i, adjLs, vis);
}
}
// Return the count
return cnt;
}
}
// Main function to test the solution
let adj = [
[1, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[1, 0, 0, 1]
];
// Creating an instance of Solution class
let sol = new Solution();
// Function call to find the provinces in the given graph
let ans = sol.numProvinces(adj);
console.log("The number of provinces in the given graph is:", ans);
