medium-level-graph.cpp

// 🌐 🟡 MEDIUM GRAPH TOPICS (Interview Level)

// 👉 Focus: Applying traversal + logic

// Cycle detection in directed graph ⭐⭐⭐
// Topological sort (DFS + BFS/Kahn’s Algorithm) ⭐⭐⭐
// Bipartite graph check ⭐⭐⭐
// Shortest path in unweighted graph (BFS) ⭐⭐
// Dijkstra’s Algorithm ⭐⭐⭐
// Bellman-Ford Algorithm ⭐⭐
// Detect negative cycle ⭐⭐
// Multi-source BFS ⭐⭐
// Grid problems (shortest path in matrix) ⭐⭐⭐
// Rotten oranges problem ⭐⭐
// Number of provinces (DFS/BFS)
// Word ladder ⭐⭐⭐
// Clone graph ⭐⭐
// Course schedule (topological sort) ⭐⭐⭐

// 👉 Goal: Solve most OA problems






// 1.🔝 2. Topological Sort ⭐⭐⭐
// 📐 Idea
// Linear ordering:
// u→v⇒u comes before v
// DAG (Directed Acyclic Graph) only
// Algorithm:
// 1. DFS-based:
// - Perform DFS and push nodes to stack after visiting all neighbors
// - Pop from stack to get topological order
// 2. Kahn’s Algorithm (BFS-based):
// - Compute in-degrees
// - Enqueue nodes with in-degree 0
// - Dequeue and reduce in-degrees of neighbors
// - Enqueue new nodes with in-degree 0
// Example: Graph with edges (5,2), (5,0), (4,0), (4,1), (2,3), (3,1)
// Topological order: 5 → 4 → 2 → 3 → 1 → 0
// input:
// 6 6
// 5 2
// 5 0
// 4 0
// 4 1
// 2 3
// 3 1
// output:
// Topological order: 5 4 2 3 1 0
// Note: Multiple valid topological orders may exist.
// C++ Implementation of Kahn’s Algorithm for Topological Sort

// (A) DFS Method
// push after recursion → reverse order
// (B) Kahn’s Algorithm (BFS)
// use in-degree






// (A) DFS Method

#include<bits/stdc++.h>
using namespace std;
void dfs(int node,vector<vector<int>>&adj,vector<bool>&visited,stack<int>&st){
    visited[node]=true;
    for(int neighbor:adj[node]){
        if(!visited[neighbor]){
            dfs(neighbor,adj,visited,st);
        }
    }
    st.push(node);// Push after visiting all neighbors
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>>adj(n);
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
    }
    vector<bool>visited(n,false);
    stack<int>st;
    for(int i=0;i<n;i++){
        if(!visited[i]){
            dfs(i,adj,visited,st);
        }
    }
    cout<<"Topological order: ";
    while(!st.empty()){
        cout<<st.top()<<" ";
        st.pop();
    }
    cout<<endl;
    return 0;
}



// (B) Kahn’s Algorithm (BFS)
// use in-degree
//algorithem:
// 1. Compute in-degrees
// 2. Enqueue nodes with in-degree 0
// 3. Dequeue and reduce in-degrees of neighbors
// 4. Enqueue new nodes with in-degree 0
// Example: Graph with edges (5,2), (5,0), (4,0), (4,1), (2,3), (3,1)
// Topological order: 5 → 4 → 2 → 3 → 1 → 0
// input:
// 6 6
// 5 2
// 5 0
// 4 0
// 4 1
// 2 3
// 3 1
// output:
// Topological order: 5 4 2 3 1 0
// Note: Multiple valid topological orders may exist.
// C++ Implementation of Kahn’s Algorithm for Topological Sort


#include<bits/stdc++.h>
using namespace std;
void kahnTopologicalSort(vector<vector<int>>&adj){
    int n=adj.size();
    vector<int>inDegree(n,0);
    // Compute in-degrees
    for(int u=0;u<n;u++){
        for(int v:adj[u]){
            inDegree[v]++;
        }
    }
    queue<int>q;
    // Enqueue nodes with in-degree 0
    for(int i=0;i<n;i++){
        if(inDegree[i]==0){
            q.push(i);
        }
    }
    vector<int>topologicalSort;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        topologicalSort.push_back(u);
        for(int v:adj[u]){
            inDegree[v]--;
            if(inDegree[v]==0){
                q.push(v);
            }
        }
    }
      // Step 4: Cycle check
    if (topologicalSort.size() != n) {
        cout << "Cycle detected! Topological sort not possible.\n";
        return;
    }
    // Print topological order
    cout<<"Topological order: ";
    for(int node:topologicalSort){
        cout<<node<<" ";
    }
    cout<<endl;
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>>adj(n);
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
    }
    kahnTopologicalSort(adj);
    return 0;
}





// ⚫ 3. Bipartite Graph ⭐⭐⭐
// 📐 Idea : used bfs or dfs
// A graph is bipartite if we can split its vertices into two disjoint sets U and V such that every edge connects a vertex in U to one in V. In other words, there are no edges between vertices within the same set.
// 👉 Use coloring (0/1)

// Divide nodes into 2 sets:
// U and V
// U∪V=All nodes
// U∩V=∅
// Edges only between U and V
// No edges within same set
// 👉 Use coloring (0/1)
// Divide nodes into 2 sets:
// U and V
//algorithem:
// 1. Initialize a color array with -1 (uncolored)
// 2. For each unvisited node, perform BFS/DFS:
// - Color the starting node with color 0
// - For each neighbor:
// - If uncolored, color with opposite color and enqueue
// - If colored and same color, graph is not bipartite
// U∪V=All nodes
//approach: 

// U∪V,no edges within same set

// 👉 Use coloring (0/1)
//input:
// 5 4
// 0 1
// 1 2
// 2 3
// 3 0
// output:
// Graph is not bipartite
// input:
// 5 4
// 0 1
// 0 2
// 1 3
// 3 0
// output:
// Graph is not bipartite

#include<bits/stdc++.h>
using namespace std;
void bfs(int start,vector<vector<int>>&adj,vector<int>&color){
    queue<int>q;
    q.push(start);
    color[start]=0; // Start coloring with 0
    while(!q.empty()){
        int node=q.front();
        q.pop();
        for(int neighbor: adj[node]){
            if(color[neighbor]==-1){// Uncolored
                color[neighbor]=1-color[node]; // Color with opposite color
                q.push(neighbor);
        }
        else if(color[neighbor]==color[node]){// Same color, not bipartite
            cout<<"Graph is not bipartite\n";
            exit(0);
         }
        
        }
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>>adj(n);
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u); // Undirected graph
    }
    vector<int>color(n,-1); // -1: uncolored
    for(int i=0;i<n;i++){
        if(color[i]==-1){
            bfs(i,adj,color);
        }
    }
    cout<<"Graph is bipartite\n";
    return 0;
}





// 📏 4. Shortest Path (Unweighted) ⭐⭐
// 📐 Idea
// dist[v]=dist[u]+1

// 👉 Use BFS
// Unweighted graph: all edges have same weight (1)
// Shortest path: minimum edges from source to destination
// Algorithm:
// 1. Initialize a distance array with -1 (unvisited)
// 2. Enqueue source node with distance 0
// 3. While queue not empty:
// - Dequeue node u
// - For each neighbor v:
// - If unvisited, set dist[v]=dist[u]+1 and enqueue v
// Example: Graph with edges (0,1), (0,2), (1,3), (2,3)
// Shortest path from 0 to 3 is 2 (0→1→3 or 0→2→3)
// input:
// 4 4
// 0 1
// 0 2
// 1 3
// 2 3
// 0 3
// output:
// Shortest path from 0 to 3 is 2
//logic:
// dist[v]=dist[u]+1
// C++ Implementation of BFS for Shortest Path in Unweighted Graph




#include<bits/stdc++.h>
using namespace std;
int bfs(int source,int destination,vector<vector<int>>&adj){
    int n=adj.size();
    vector<int>dist(n,-1); // -1: unvisited
    queue<int>q;
    q.push(source);
    dist[source]=0; // Distance to source is 0
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int neighbor: adj[u]){
            if(dist[neighbor]==-1){// Unvisited
                dist[neighbor]=dist[u]+1; //Update distance
                q.push(neighbor);
                if(neighbor==destination){
                    return dist[neighbor];// Return distance to destination
                }
            }
        }
    }
    return -1; // Destination not reachable
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>>adj;
    adj.resize(n);
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u); // Undirected graph
    }
    int source,destination;
    cin>>source>>destination;
    int shortestPath=bfs(source,destination,adj);
    if(shortestPath!=-1){
        cout<<"Shortest path from "<<source<<" to "<<destination<<" is "<<shortestPath<<endl;
    }
    else{
        cout<<"Destination not reachable from source\n";
    }
    return 0;

}




// 🛣️ 5. Dijkstra’s Algorithm ⭐⭐⭐
// 📐 Idea
// dist[v]=min(dist[v],dist[u]+w)

// 👉 Works for positive weights
// Shortest path: minimum total weight from source to destination
// Algorithm:
// 1. Initialize a distance array with infinity
// 2. Use a priority queue to store (distance, node) pairs
// 3. Enqueue source node with distance 0
// 4. While priority queue not empty:
// - Dequeue node u with smallest distance
// - For each neighbor v with edge weight w:
// - If dist[u]+w<dist[v], update dist[v] and enqueue (dist[v], v)
// Example: Graph with edges (0,1,4), (0,2,1), (1,2,2), (1,3,5), (2,3,8)
// Shortest path from 0 to 3 is 8 (0→2→3)
// input:
// 4 5
// 0 1 4
// 0 2 1
// 1 2 2
// 1 3 5
// 2 3 8
// 0 3
// output:
// Shortest path from 0 to 3 is 8
// C++ Implementation of Dijkstra’s Algorithm for Shortest Path in Weighted Graph
// dist[v]=min(dist[v],dist[u]+w)
// Works for positive weights
// Shortest path: minimum total weight from source to destination
// Algorithm:
//graph: undirected, weighted




#include<bits/stdc++.h>
using namespace std;
int dijkstra(int source,int destination,vector<vector<pair<int,int>>>&adj){
    int n=adj.size();
    vector<int>dist(n,INT_MAX); // Initialize distances with infinity
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq; // Min-heap
    pq.push({0,source}); // (distance, node)
    dist[source]=0; // Distance to source is 0
    while(!pq.empty()){
        pair<int,int> top=pq.top();
        pq.pop();
        int currentDist=top.first;
        int u=top.second;
        if(currentDist>dist[u]) continue; // Skip if we already have a shorter path
        for(auto edge:adj[u]){
            int v=edge.first;
            int w=edge.second;
            if(dist[u]+w<dist[v]){
                dist[v]=dist[u]+w;
                pq.push({dist[v],v});
            }
        }
    }
    return dist[destination]==INT_MAX?-1:dist[destination];
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,int>>>adj(n); // Adjacency list with (neighbor, weight)
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w}); // Undirected graph
    }
    int source,destination;
    cin>>source>>destination;
    int shortestPath=dijkstra(source,destination,adj);
    if(shortestPath!=-1){
        cout<<"Shortest path from "<<source<<" to "<<destination<<" is: "<<shortestPath<<endl;
    }
    else{
        cout<<"Destination not reachable from source\n";
    }
    return 0;
}







// ⚡ 6. Bellman-Ford ⭐⭐
// 📐 Idea
// Works for negative weights (no negative cycles)
// Shortest path: minimum total weight from source to destination
// Algorithm:
// 1. Initialize a distance array with infinity
// 2. Set distance to source as 0
// 3. Relax edges repeatedly (V-1 times):
// - For each edge (u,v) with weight w:
// - If dist[u]+w<dist[v], update dist[v]
// 4. Check for negative-weight cycles:
// - For each edge (u,v) with weight w:
// - If dist[u]+w<dist[v], negative cycle exists
// Example: Graph with edges (0,1,4), (0,2,1), (1,2,-2), (1,3,5), (2,3,8)
// Shortest path from 0 to 3 is 7 (0→1→2→3)
// input:
// 4 5
// 0 1 4
// 0 2 1
// 1 2 -2
// 1 3 5
// 2 3 8
// 0 3
// output:
// Shortest path from 0 to 3 is 7
// C++ Implementation of Bellman-Ford Algorithm for Shortest Path in Weighted Graph
// Relax edges:dist[v]=min(dist[v],dist[u]+w)
// V−1 times
// Works for negative weights (no negative cycles)
// Shortest path: minimum total weight from source to destination
//graph: directed, weighted
// Check for negative cycles
// If dist[u]+w<dist[v], negative cycle exists





#include<bits/stdc++.h>
using namespace std;
int bellmanFord(int source,int destination,vector<vector<tuple<int,int,int>>>&adj){
    int n=adj.size();
    vector<int>dist(n,INT_MAX); // Initialize distances with infinity
    dist[source]=0; // Distance to source is 0
    // Relax edges repeatedly (V-1 times)
    for(int i=0;i<n-1;i++){
        for(int u=0;u<n;u++){
            for(auto edge:adj[u]){
                int u=get<0>(edge);
                int v=get<1>(edge);
                 int w = get<2>(edge);
                if(dist[u]!=INT_MAX && dist[u]+w<dist[v]){
                    dist[v]=dist[u]+w;
                }
            }

        }

    }
    // Check for negative-weight cycles
    for(int u=0;u<n;u++){
        for(auto edge:adj[u]){
             int u=get<0>(edge);
            int v=get<1>(edge);
            int w=get<2>(edge);
            if(dist[u]!=INT_MAX && dist[u]+w<dist[v]){
                cout<<"Negative cycle detected! Shortest path not possible.\n";
                return -1;
            }
        }
    }
    return dist[destination]==INT_MAX?-1:dist[destination];

}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<tuple<int,int,int>>>adj(n); // Adjacency list with (neighbor, weight)
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back(make_tuple(u,v,w)); // Directed graph
    }
    int source,destination;
    cin>>source>>destination;
    int shortestPath=bellmanFord(source,destination,adj);
    if(shortestPath!=-1){
        cout<<"Shortest path from "<<source<<" to "<<destination<<" is: "<<shortestPath<<endl;
    }
    else{
        cout<<"Destination not reachable from source or negative cycle detected.\n";
    }
    return 0;
}





//second method for bellman ford
#include <bits/stdc++.h>
using namespace std;

int bellmanFord(int source, int destination, int n, vector<tuple<int,int,int>>& edges) {
    vector<int> dist(n, INT_MAX);
    dist[source] = 0;

    // Step 1: Relax edges (V-1 times)
    for (int i = 0; i < n - 1; i++) {
        for (auto edge : edges) {
            int u = get<0>(edge);
            int v = get<1>(edge);
            int w = get<2>(edge);
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // Step 2: Detect negative cycle
    for (auto edge : edges) {
        int u = get<0>(edge);
        int v = get<1>(edge);
        int w = get<2>(edge);
        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            cout << "Negative cycle detected!\n";
            return -1;
        }
    }

    return dist[destination] == INT_MAX ? -1 : dist[destination];
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<tuple<int,int,int>> edges;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w}); // Directed edge
    }

    int source, destination;
    cin >> source >> destination;

    int ans = bellmanFord(source, destination, n, edges);

    if (ans != -1)
        cout << "Shortest path from " << source << " to " << destination << " is: " << ans << endl;
    else
        cout << "Destination not reachable or negative cycle detected\n";

    return 0;
}





// 🔥 8. Multi-source BFS ⭐⭐

// 👉 Push all sources initially
// Multiple sources: start BFS from all sources simultaneously
// Shortest path: minimum edges from any source to destination
// Algorithm:
// 1. Initialize a distance array with -1 (unvisited)
// 2. Enqueue all source nodes with distance 0
// 3. While queue not empty:
// - Dequeue node u
// - For each neighbor v:
// - If unvisited, set dist[v]=dist[u]+1 and enqueue v
// Example: Graph with edges (0,1), (0,2), (1,3), (2,3) and sources [0,1]
// Shortest path from sources to 3 is 1 (1→3)
// input:
// 4 4
// 0 1
// 0 2
// 1 3
// 2 3
// 2
// 0 1
// 3
// output:
// Shortest path from sources to 3 is 1
// C++ Implementation of Multi-source BFS for Shortest Path in Unweighted Graph
// dist[v]=dist[u]+1





#include<bits/stdc++.h>
using namespace std;
int multiSourceBFS(vector<int>&sources,int destination,vector<vector<int>>&adj){
    int n=adj.size();
    vector<int>dist(n,-1);// -1: unvisited
    queue<int>q;
    // Enqueue all source nodes with distance 0
    for(int source:sources){
        q.push(source);
        dist[source]=0; // Distance to source is 0

    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int neighbor: adj[u]){
            if(dist[neighbor]==-1){
                dist[neighbor]=dist[u]+1;// Update distance
                q.push(neighbor);
                if(neighbor==destination){
                    return dist[neighbor]; // Return distance to destination
                }
            }
        }

    }
    return -1; // Destination not reachable

}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>>adj(n);
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u); // Undirected graph
    }
    int k;
    cin>>k;
    vector<int>sources(k);
    for(int i=0;i<k;i++){
        cin>>sources[i];
    }
    int destination;
    cin>>destination;
    int shortestPath=multiSourceBFS(sources,destination,adj);
    if(shortestPath!=-1){
        cout<<"Shortest path from sources to "<<destination<<" is: "<<shortestPath<<endl;
    }
    else{
        cout<<"Destination not reachable from sources\n";
    }
    return 0;
}




//🟩 9. Grid Shortest Path
// 👉 Use BFS
// Grid: 2D matrix with obstacles (0=free, 1=obstacle)
// Shortest path: minimum steps from source to destination
// Algorithm:
// 1. Initialize a distance matrix with -1 (unvisited)
// 2. Enqueue source cell with distance 0
// 3. While queue not empty:
// - Dequeue cell (x,y)
// - For each direction (up, down, left, right):
// - If new cell (nx,ny) is within bounds, not an obstacle, and unvisited:
// - Set dist[nx][ny]=dist[x][y]+1 and enqueue (nx,ny)
// Example: Grid [[0,0,0],[0,1,0],[0,0,0]] with source (0,0) and destination (2,2)
// Shortest path is 4 (0,0)→(1,0)→(2,0)→(2,1)→(2,2)
// input:
// 3 3
// 0 0 0
// 0 1 0
// 0 0 0
// 0 0
// 2 2
// output:
// Shortest path from (0,0) to (2,2) is: 4
// C++ Implementation of BFS for Shortest Path in Grid with Obstacles
// dist[nx][ny]=dist[x][y]+1
// Grid: 2D matrix with obstacles (0=free, 1=obstacle)
// Shortest path: minimum steps from source to destination
// Algorithm:
// 1. Initialize a distance matrix with -1 (unvisited)
//drid: 2D matrix with obstacles (0=free, 1=obstacle)




#include<bits/stdc++.h>
using namespace std;
int bfs(pair<int,int>source,pair<int,int>destination,vector<vector<int>>&grid){
    int m=grid.size();
    int n=grid[0].size();
    vector<vector<int>>dist(m,vector<int>(n,-1)); // -1: unvisited
    queue<pair<int,int>>q;
    q.push(source);
    dist[source.first][source.second]=0; // Distance to source is 0
    vector<pair<int,int>>direction({{0,1},{0,-1},{1,0},{-1,0}}); // right, left, down, up
    while(!q.empty()){
        pair<int,int>cell=q.front();
        q.pop();
        int x=cell.first;
        int y=cell.second;
        for(auto dir:direction){
            int nx=x+dir.first;
            int ny=y+dir.second;
            for(int i=0;i<4;i++){
                if(nx>=0 && nx<m && ny>=0 && ny<n && grid[nx][ny]==0 && dist[nx][ny]==-1){
                    dist[nx][ny]=dist[x][y]+1;
                    q.push({nx,ny});
                }
            }
        }
    }
    return dist[destination.first][destination.second];
}
int main(){
    int m,n;
    cin>>m>>n;
    vector<vector<int>>grid(m,vector<int>(n));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>grid[i][j];
        }
    }
    pair<int,int>source,destination;
    cin>>source.first>>source.second;
    cin>>destination.first>>destination.second;
    int shortestPath=bfs(source,destination,grid);
    if(shortestPath!=-1){
        cout<<"Shortest path from ("<<source.first<<","<<source.second<<") to ("<<destination.first<<","<<destination.second<<") is: "<<shortestPath<<endl;
    }
    else{
        cout<<"Destination not reachable from source\n";
    }
    return 0;
}




// 🍊 10. Rotten Oranges ⭐⭐

// 👉 Multi-source BFS
// Grid: 2D matrix with oranges (0=empty, 1=fresh, 2=rotten)
// Time to rot: minimum minutes for all fresh oranges to become rotten
// Algorithm:
// 1. Enqueue all rotten oranges with time 0
// 2. While queue not empty:
// - Dequeue cell (x,y) with time t
// - For each direction (up, down, left, right):
// - If new cell (nx,ny) has a fresh orange:
// - Change it to rotten, enqueue (nx,ny) with time t+1
// 3. After BFS, check if any fresh orange remains
// Example: Grid [[2,1,1],[1,1,0],[0,1,1]]
// Time to rot is 4 (2→1→1→0→1)
// input:
// 3 3
// 2 1 1
// 1 1 0
// 0 1 1
// output:
// Time to rot all oranges is: 4
// C++ Implementation of Multi-source BFS for Rotten Oranges Problem
// Multi-source BFS




#include<bits/stdc++.h>
using namespace std;
int rottenOranges(vector<vector<int>>&grid){
    int m=grid.size();
    int n=grid[0].size();
    queue<pair<int,int>>q;
    int freshCount=0;
    // Enqueue all rotten oranges and count fresh oranges
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]==2){
                q.push({i,j});
            }
            else if(grid[i][j]==1){
                freshCount++;
            }
        }

    }
    if(freshCount==0) return 0; // No fresh oranges to rot
    vector<pair<int,int>>direction({{0,1},{0,-1},{1,0},{-1,0}}); // right, left, down, up
    int time=0;
    while(!q.empty()){
        int size=q.size();
         bool changed=false;  // ✅ FIX added
        for(int i=0;i<size;i++){
            pair<int,int>cell=q.front();
            q.pop();
            int x=cell.first;
            int y=cell.second;
            for(auto dir:direction){
                int nx=x+dir.first;
                int ny=y+dir.second;
                if(nx>=0 && nx<m && ny>=0 && ny<n && grid[nx][ny]==1){
                    grid[nx][ny]=2; // Rot the fresh orange
                    q.push({nx,ny});
                    freshCount--;
                     changed=true; // ✅ FIX added
                }
            }

        }
      if(changed) time++; // ✅ FIX applied // Increment time after each level of BFS
    }
    // Some fresh oranges are unreachable
      // ✅ FIX applied here
    if(freshCount==0) return time;
    return -1;
}
int main(){
    int m,n;
    cin>>m>>n;
    vector<vector<int>>grid(m,vector<int>(n));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>grid[i][j];
        }
    }
    int timeToRot=rottenOranges(grid);
    if(timeToRot!=-1){
        cout<<"Time to rot all oranges is: "<<timeToRot<<endl;
    }
    else{
        cout<<"Some fresh oranges are unreachable"<<endl;
    }
    return 0;
}








// 🧠 11. Word Ladder ⭐⭐⭐

// 👉 BFS on words (change 1 char)
// Words: list of valid words
// Start and end words
// Shortest transformation: minimum steps to change start to end by changing one char at a time, with all intermediate words in the list
// Algorithm:
// 1. Create a set of words for O(1) lookups
// 2. Enqueue start word with distance 1
// 3. While queue not empty:
// - Dequeue word w with distance d
// - If w is end word, return d
// - For each character in w:
// - For each letter from 'a' to 'z':
// - Change character to new letter to form new word nw
// - If nw is in word set, enqueue nw with distance d+1 and remove from set
// Example: Start="hit", End="cog", Words=["hot","dot","dog","cot","cog"]
// Shortest transformation is 5 (hit→hot→dot→dog→cog)
// input:
// hit
// cog
// 5
// hot
// dot
// dog
// cot
// cog
// output:
// Shortest transformation from hit to cog is: 5
// C++ Implementation of BFS for Word Ladder Problem




#include<bits/stdc++.h>
using namespace std;
int wordLadder(string start,string end,vector<string>&wordlist){
    unordered_set<string>wordset(wordlist.begin(),wordlist.end());
    if(wordset.find(end)==wordset.end()){
        return 0; // End word not in list
    }
    queue<pair<string,int>>q;
    q.push({start,1}); // (current word, distance)
    while(!q.empty()){
        pair<string,int> front=q.front();
        q.pop();
        string word=front.first;
        int dist=front.second;
        if(word==end){
            return dist;
        }
        for(int i=0;i<word.length();i++){
            for(char c='a';c<='z';c++){
                if(c==word[i]) continue;
                string newWord=word;
                newWord[i]=c;
                if(wordset.find(newWord)!=wordset.end()){
                    q.push({newWord,dist+1});
                    wordset.erase(newWord);
                }
            }
        }
    }
    return 0; // End word not reachable
}
int main(){
    string start,end;
    cin>>start>>end;
    int n;
    cin>>n;
    vector<string>wordlist(n);
    for(int i=0;i<n;i++){
        cin>>wordlist[i];
    }
    int shortestTransformation=wordLadder(start,end,wordlist);
    if(shortestTransformation!=0){
        cout<<"Shortest transformation from "<<start<<" to "<<end<<" is: "<<shortestTransformation<<endl;
    }
    else{
        cout<<"End word not reachable from start word\n";
    }
    return 0;
}




// 🎓 12. Course Schedule ⭐⭐⭐

// 👉 Topological sort + cycle detection
// Courses: 0 to n-1
// Prerequisites: list of pairs (a,b) meaning b must be taken before a
// Possible to finish all courses: no cycles in prerequisite graph
// Algorithm:
// 1. Build adjacency list and compute in-degrees
// 2. Enqueue courses with in-degree 0
// 3. While queue not empty:
// - Dequeue course c and add to order
// - For each neighbor n of c:
// - Decrease in-degree of n
// - If in-degree of n becomes 0, enqueue n
// 4. If order contains all courses, return true; otherwise, false
// Example: Courses=4, Prerequisites=[(1,0),(2,0),(3,1),(3,2)]
// Possible to finish all courses: true (0→1→3 and 0→2→3)
// input:
// 4 4
// 1 0
// 2 0
// 3 1
// 3 2
// output:
// All courses can be finished
// C++ Implementation of Course Schedule Problem using Topological Sort and Cycle Detection
// Topological sort + cycle detection



 #include<bits/stdc++.h>
    using namespace std;
    bool canFinish(int numCourses, vector<pair<int,int>>& prerequisites) {
        vector<vector<int>>adj(numCourses);
        vector<int>inDegree(numCourses,0);
        // Build adjacency list and compute in-degrees
        for(auto pre:prerequisites){
            int a=pre.first;
            int b=pre.second;
            adj[b].push_back(a); // b must be taken before a
            inDegree[a]++;
        }
        queue<int>q;
        // Enqueue courses with in-degree 0
        for(int i=0;i<numCourses;i++){
            if(inDegree[i]==0){
                q.push(i);
            }
        }
        int count=0; // Count of courses that can be finished
        while(!q.empty()){
            int course=q.front();
            q.pop();
            count++;
            for(int neighbor:adj[course]){
                inDegree[neighbor]--;
                if(inDegree[neighbor]==0){
                    q.push(neighbor);
                }
            }
        }
        return count==numCourses; // If all courses can be finished
    }
    int main(){
        int numCourses,m;
        cin>>numCourses>>m;
        vector<pair<int,int>>prerequisites(m);
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            prerequisites[i]={a,b};
        }
        if(canFinish(numCourses,prerequisites)){
            cout<<"All courses can be finished\n";
        }
        else{
            cout<<"Some courses cannot be finished due to cyclic dependencies\n";
        }
        return 0;
    }