```class Solution
{
public:
//Function to find the level of node X.
using pi = pair<int,int>;
int nodeLevel(int V, vector<int> adj[], int X)
{
// code here
vector<bool> vis(V, false);
queue<pi> q;
q.push({0, 0});
vis = true;
while(!q.empty()){
auto curr = q.front();q.pop();
if(curr.first == X)
return curr.second;
}
}
}
return -1;
}
};```
```class Solution {
public:
int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
vector<vector<int>> gr(n+1);
vector<int> indegree(n+1, 0), prev_time(n+1, 0);
for(auto& edge : relations){
gr[edge].push_back(edge);
indegree[edge]++;
}
time.insert(time.begin(), 0);
queue<int> q;
for(int i =1; i <= n; i++)
if(indegree[i] == 0)
q.push(i);
while(!q.empty()){
int node = q.front();q.pop();
}
}
int ans = 0;
for(int i =1 ; i < n + 1; ++i){
ans = max(ans, time[i]+prev_time[i]);
}
return ans;
}
};```
```class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
vector<vector<int>> graph(n);
vector<int> indegree(n, 0), ans;

for(auto e : edges){
graph[e].push_back(e);
graph[e].push_back(e);
indegree[e]++;
indegree[e]++;
}
queue<int> q;
for(int i = 0; i < n ;i++)
if(indegree[i] == 1)
q.push(i), indegree[i]--;

while(!q.empty()){
int s = q.size();
ans.clear();
for(int i = 0 ; i < s ;i++){
int curr = q.front(); q.pop();
ans.push_back(curr);
for(auto child : graph[curr])
{
indegree[child]--;
if(indegree[child] == 1)
q.push(child);
}
}
}
if(n == 1)ans.push_back(0);
return ans;
}
};```
```class Solution {
using Index = pair<int, int>;
vector<Index> directions =
{
{-1, -1},
{-1, 0},
{-1, 1},
{0, -1},
{0, 1},
{1, -1},
{1, 0},
{1, 1}
};

public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid)
{
const int n = grid.size();
if (grid == 1 || grid[n - 1][n - 1] == 1)
return -1;

if (n == 1)
return 1;

int distance = 1;
Index target = {n - 1, n - 1};
queue<Index> q;
q.push({0, 0});
grid = 1;
while (!q.empty())
{
const int levelSize = q.size();
for (int i = 0; i < levelSize; i++)
{
Index curr = q.front();
q.pop();
for (const Index& diff : directions)
{
Index next = {curr.first + diff.first, curr.second + diff.second};
if (next.first >= 0 && next.first < n && next.second >= 0 && next.second < n
&& grid[next.first][next.second] == 0)
{
if (next == target)
return distance + 1;
grid[next.first][next.second] = 1;
q.push(next);
}
}
}
distance++;
}
return -1;
}
};```
```#include<stdio.h>

void BFS(int);
int graph, visited,total;

main()
{
int i,j;
printf("\nEnter the total number of vertices in graph\n");
scanf("%d",&total);
for(i=0;i<total;i++)
{
for(j=0;j<total;j++)
{
scanf("%d",&graph[i][j]);
}
}
for(i=0;i<total;i++)
{
visited[i] = 0;
}
printf("\nBFS traversal is \n");
BFS(0);
}
void BFS(int vertex)
{
int j;
printf("%d\t",vertex);
visited[vertex] = 1;
for(j=0;j<total;j++)
{
if(!visited[j] && graph[vertex][j] == 1 )
{
BFS(j);
}
}
}```
```class Solution {
public:
int closedIslands(vector<vector<int>>& matrix, int N, int M) {
// Code here
queue<pair<int,int>> q;
for(int i = 0; i < N ; i++){
for(int j = 0; j < M; j++){
if(matrix[i][j] == 1 && (i == 0 || j == 0 || i == N-1 || j == M-1))
q.push({i,j}),matrix[i][j] = 0;
}
}
auto bfs = [&q,&matrix,N,M]()->void{
auto isSafe = [N, M](int x, int y)->bool{
return x>=0 && y>=0 && x<N && y<M;
};
while(!q.empty()){
auto curr = q.front();
q.pop();
vector<pair<int,int>> dir{
{1,0},
{0,-1},
{-1,0},
{0,1}
};
for(auto p : dir){
int x = p.first+ curr.first , y = p.second + curr.second;
if(isSafe(x, y) && matrix[x][y] == 1 )
q.push({x,y}), matrix[x][y] = 0;
}
}
};
bfs();
int ans = 0;
for(int i = 0; i < N; i++){
for(int j = 0 ; j<M; j++){
if(matrix[i][j]){
matrix[i][j] = 0;
q.push({i,j});
bfs(),ans++;
}
}
}
return ans;
}
};```
star

Thu Oct 19 2023 07:20:10 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/level-of-nodes-1587115620/1

#bfs #graphs #easy
star

Wed Oct 18 2023 10:50:28 GMT+0000 (Coordinated Universal Time)

#parallelcourses3 #graphs #bfs #dynamicprogramming #topologicalsort #arrays
star

Tue Oct 10 2023 14:44:39 GMT+0000 (Coordinated Universal Time)

#trees #topologicalsort #minimumheighttrees #bfs
star

Thu Jun 01 2023 08:35:21 GMT+0000 (Coordinated Universal Time) https://leetcode.com/submissions/detail/961503088/

#c++ #bfs #shortest_path_binmat
star

Mon May 22 2023 12:25:11 GMT+0000 (Coordinated Universal Time)

#algo #bfs #search
star

Thu May 18 2023 19:59:59 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/find-number-of-closed-islands/1

#bfs #closedislands #lambda_functions

#### Save snippets that work with our extensions   