123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116
#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 call to find the number of
connected components in the given graph */
int findNumberOfComponent(int E, int V,
vector<vector<int>> &edges) {
// To store adjacency list
vector<int> adjLs[V];
// Add edges to adjacency list
for(int i=0; i < E; i++) {
adjLs[edges[i][0]].push_back(edges[i][1]);
adjLs[edges[i][1]].push_back(edges[i][0]);
}
// Visited array
int vis[V] = {0};
// Variable to store number of components
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 using any traversal */
bfs(i, adjLs, vis);
//dfs(i, adjLs, vis);
}
}
// Return the count
return cnt;
}
};
int main() {
int V = 4, E = 2;
vector<vector<int>> edges = {
{0, 1},
{1, 2}
};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to find the number of
connected components in the given graph */
int ans = sol.findNumberOfComponent(E, V, edges);
cout << "The number of components in the given graph is: " << ans;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109
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 call to find the number of
connected components in the given graph */
public int findNumberOfComponent(int E, int V,
List<List<Integer>> edges) {
// To store adjacency list
List<Integer>[] adjLs = new ArrayList[V];
for (int i = 0; i < V; i++) {
adjLs[i] = new ArrayList<>();
}
// Add edges to adjacency list
for (int i = 0; i < E; i++) {
adjLs[edges.get(i).get(0)].add(edges.get(i).get(1));
adjLs[edges.get(i).get(1)].add(edges.get(i).get(0));
}
// Visited array
boolean[] vis = new boolean[V];
// Variable to store number of components
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 using any traversal */
bfs(i, adjLs, vis);
// dfs(i, adjLs, vis);
}
}
// Return the count
return cnt;
}
public static void main(String[] args) {
int V = 4, E = 2;
List<List<Integer>> edges = Arrays.asList(
Arrays.asList(0, 1),
Arrays.asList(1, 2)
);
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to find the number of
connected components in the given graph */
int ans = sol.findNumberOfComponent(E, V, edges);
System.out.println("The number of components in the given graph is: " + ans);
}
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697
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 call to find the number of
# connected components in the given graph
def findNumberOfComponent(self, E, V, edges):
# To store adjacency list
adjLs = [[] for _ in range(V)]
# Add edges to adjacency list
for i in range(E):
adjLs[edges[i][0]].append(edges[i][1])
adjLs[edges[i][1]].append(edges[i][0])
# Visited array
vis = [0] * V
# Variable to store number of components
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 using any traversal
self.bfs(i, adjLs, vis)
# self.dfs(i, adjLs, vis)
# Return the count
return cnt
if __name__ == "__main__":
V = 4
E = 2
edges = [
[0, 1],
[1, 2]
]
# Creating an instance of
# Solution class
sol = Solution()
# Function call to find the number of
# connected components in the given graph
ans = sol.findNumberOfComponent(E, V, edges)
print("The number of components in the given graph is:", ans)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103
class Solution {
// Function for BFS traversal
bfs(node, adjLs, vis) {
// Mark the node as visited
vis[node] = 1;
// Queue required for BFS traversal
const 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
const i = q.shift();
// Traverse its unvisited neighbours
for (const 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 (const it of adjLs[node]) {
if (!vis[it]) {
// Recursively perform DFS
this.dfs(it, adjLs, vis);
}
}
}
/* Function call to find the number of
connected components in the given graph */
findNumberOfComponent(E, V, edges) {
// To store adjacency list
const adjLs = Array.from({ length: V }, () => []);
// Add edges to adjacency list
for (let i = 0; i < E; i++) {
adjLs[edges[i][0]].push(edges[i][1]);
adjLs[edges[i][1]].push(edges[i][0]);
}
// Visited array
const vis = new Array(V).fill(0);
// Variable to store number of components
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 using any traversal */
this.bfs(i, adjLs, vis);
// this.dfs(i, adjLs, vis);
}
}
// Return the count
return cnt;
}
}
const main = () => {
const V = 4;
const E = 2;
const edges = [
[0, 1],
[1, 2]
];
// Creating an instance of
// Solution class
const sol = new Solution();
// Function call to find the number of
// connected components in the given graph
const ans = sol.findNumberOfComponent(E, V, edges);
console.log("The number of components in the given graph is:", ans);
};
main();
