Graph¶

/*Question:-

Count the number of undirected graphs that can be formed with n vertices.

Approach:-
- calculate the number of edges with formula n*n-1/2
- return pow(2,edges) 

Complexity Analysis:-

Time Complexity = O(1)
Space Complexity = O(1)
*/

int countingGraphs(int n)
{
    int edges = (n*(n-1))/2;
    return pow(2,edges);
}

/*
Question:
Given the adjacency matrix representation of an undirected graph, your task is to return the adjacency list of the graph where each adjacency list contains the vertex itself at the first position and then all its adjacent nodes.

Explanation:
- We initialize an empty adjacency list vector of vectors.
- For each vertex in the graph, we add the vertex itself as the first element of its adjacency list.
- Then, for each edge (u, v) in the graph, we add v to the adjacency list of u and u to the adjacency list of v.
- Finally, we return the adjacency list.

Time Complexity:
- The time complexity is O(m), where m is the number of edges in the graph, as we iterate through each edge once.

Space Complexity:
- The space complexity is O(n + 2 * m), where n is the number of vertices and 2 * m is the total number of elements in all adjacency lists, as each edge is represented twice (once in the adjacency list of u and once in the adjacency list of v).

*/

vector<vector<int>> printAdjacency(int n, int m, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        adj[i].push_back(i);
    }
    for (auto e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    return adj;
}

/*
Question:
Given a directed graph, perform Breadth First Traversal (BFS) of the graph starting from vertex 0 and visit all the nodes directly or indirectly connected to Node 0.

Explanation:
- We initialize an empty vector 'ans' to store the BFS traversal.
- We also initialize a vector 'vis' to keep track of visited nodes, initialized with 'false' for all nodes.
- We use a queue 'q' to perform BFS. We start by pushing vertex 0 into the queue and mark it as visited.
- While the queue is not empty, we pop the front element and add it to the 'ans' vector.
- For each adjacent vertex of the current node, if it has not been visited, we push it into the queue and mark it as visited.
- We continue this process until the queue becomes empty and all connected nodes are visited.
- Finally, we return the 'ans' vector containing the BFS traversal.

Time Complexity:
- The time complexity is O(V + E), where V is the number of vertices and E is the number of edges in the graph. In the worst case, we visit all the vertices and edges.

Space Complexity:
- The space complexity is O(V), where V is the number of vertices, as we use extra space for the 'vis' vector and the 'q' queue.

*/

vector<int> bfsOfGraph(int V, vector<int> adj[]) {
    vector<int> ans;
    vector<bool> vis(V, false);

    queue<int> q;
    q.push(0);
    vis[0] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        ans.push_back(node);
        for (auto i : adj[node]) {
            if (!vis[i]) {
                q.push(i);
                vis[i] = true;
            }
        }
    }

    return ans;
}

/*
Question:
Given a connected undirected graph, perform Depth First Traversal (DFS) of the graph starting from vertex 0 and visit all the nodes directly or indirectly connected to Node 0.

Explanation:
- We initialize an empty vector 'ans' to store the DFS traversal.
- We also initialize a vector 'vis' to keep track of visited nodes, initialized with 'false' for all nodes.
- We start DFS from vertex 0 by calling the recursive function 'dfs'.
- In the 'dfs' function, we push the current node into the 'ans' vector and mark it as visited.
- For each adjacent vertex of the current node, if it has not been visited, we call the 'dfs' function recursively for that vertex.
- We continue this process until all connected nodes are visited.
- Finally, we return the 'ans' vector containing the DFS traversal.

Time Complexity:
- The time complexity is O(V + E), where V is the number of vertices and E is the number of edges in the graph. In the worst case, we visit all the vertices and edges.

Space Complexity:
- The space complexity is O(V), where V is the number of vertices, as we use extra space for the 'vis' vector.

*/

void dfs(int node, vector<int> adj[], vector<int>& ans, vector<bool>& vis){
    ans.push_back(node);
    vis[node] = true;
    for(auto i : adj[node]){
        if(!vis[i])
            dfs(i, adj, ans, vis);
    }
}

vector<int> dfsOfGraph(int V, vector<int> adj[]) {
    vector<int> ans;
    vector<bool> vis(V, false);
    dfs(0, adj, ans, vis);
    return ans;
}

/*
Question:
Given an n x n matrix 'isConnected' representing connections between cities (nodes), find the total number of provinces in the graph.

Explanation:
- The problem can be solved using Depth First Search (DFS).
- We first convert the given matrix 'isConnected' into an adjacency list 'adj' representing the graph.
- We use a 'vis' vector to keep track of visited cities, initialized to 'false' for all cities.
- We initialize a variable 'ans' to store the number of provinces.
- We then perform DFS from each city and mark all directly or indirectly connected cities as visited.
- We increment the 'ans' for each unvisited city and continue the process until all cities are visited.
- Finally, we return the 'ans' which represents the total number of provinces in the graph.

Time Complexity:
- The time complexity is O(n^2), where n is the number of cities. We traverse the entire 'isConnected' matrix to construct the adjacency list.

Space Complexity:
- The space complexity is O(n), where n is the number of cities. We use extra space for the adjacency list and the 'vis' vector.

*/

void dfs(int node, vector<int> adj[], vector<bool>& vis){
    vis[node] = true;
    for(auto v : adj[node]){
        if(!vis[v])
            dfs(v, adj, vis);
    }
}

int findCircleNum(vector<vector<int>>& isConnected) {
    int ans = 0, n = isConnected.size();
    vector<int> adj[n];

    // Convert isConnected matrix into adjacency list
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(isConnected[i][j] == 1){
                adj[i].push_back(j);
            }
        }
    }

    vector<bool> vis(n, false);

    // Perform DFS to find the number of provinces
    for(int i=0; i<n; i++){
        if(!vis[i]){
            ans++;
            dfs(i, adj, vis);
        }
    }

    return ans;
}

/*
Question: 

You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Approach:

1. Use Breadth-First Search (BFS) to rot the oranges.
2. Initialize a queue to store the rotten oranges.
3. Iterate through the grid to find the rotten oranges and count the number of fresh oranges.
4. Perform BFS starting from each rotten orange and keep track of the time required to rot all the fresh oranges.
5. For each level in BFS (each minute), check adjacent cells to a rotten orange and mark them as rotten if they contain a fresh orange. Decrease the fresh count and add the newly rotten oranges to the queue.
6. Repeat this process until all fresh oranges are rotten or the queue is empty.
7. Return the time required (minutes) if all fresh oranges are rotten, otherwise, return -1.

Time Complexity: O(m * n) - where 'm' is the number of rows and 'n' is the number of columns in the grid.
Space Complexity: O(m * n) - due to the queue and the grid.

Code:
*/

int orangesRotting(vector<vector<int>>& grid) {
    int ans = -1, fresh = 0, m = grid.size(), n = grid[0].size();
    queue<pair<int, int>> q;

    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(grid[i][j] == 2) {
                q.push({i, j});
            }
            if(grid[i][j] == 1) {
                fresh++;
            }
        }
    }

    if(fresh == 0) {
        return 0;
    }

    vector<int> dr = {-1, 1, 0, 0};
    vector<int> dc = {0, 0, -1, 1};

    while(!q.empty()) {
        int k = q.size();
        while(k--) {
            auto p = q.front();
            q.pop();
            int x = p.first, y = p.second;

            for(int i = 0; i < 4; i++) {
                int nx = x + dr[i], ny = y + dc[i];
                if(nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;
                    q.push({nx, ny});
                    fresh--;
                }
            }
        }
        ans++;
    }

    return (fresh > 0) ? -1 : ans;
}

/*
QUESTION:

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

Return the modified image after performing the flood fill.

Example:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

CODE:
*/

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
    vector<vector<int>> ans(image.begin(), image.end());
    int m = image.size(), n = image[0].size();
    queue<pair<int, int>> q;
    q.push({sr, sc});
    int s = ans[sr][sc];
    ans[sr][sc] = color;

    vector<int> dr = {-1, 1, 0, 0};
    vector<int> dc = {0, 0, -1, 1};

    while (!q.empty()) {
        int siz = q.size();
        while (siz--) {
            auto p = q.front();
            q.pop();
            int x = p.first, y = p.second;
            for (int i = 0; i < 4; i++) {
                int nx = x + dr[i], ny = y + dc[i];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && ans[nx][ny] == s && ans[nx][ny] != color) {
                    ans[nx][ny] = color;
                    q.push({nx, ny});
                }
            }
        }
    }

    return ans;
}

/*
QUESTION:-

Given an undirected graph with V vertices and E edges, check whether it contains any cycle or not. Graph is in the form of adjacency list where adj[i] contains all the nodes ith node is having an edge with.

APPROACH:
- To check whether the graph contains a cycle or not, we can perform a Depth-First Search (DFS) traversal on the graph and keep track of the visited nodes.
- During the DFS traversal, if we encounter a node that is already visited and is not the parent of the current node (indicating a back edge), then there is a cycle in the graph. We need to check this condition for every node in the graph.

COMPLEXITY ANALYSIS:
- Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph. In the worst case, we may need to visit all the vertices and edges of the graph.
- Space Complexity: O(V), where V is the number of vertices. We use an additional array to keep track of visited nodes.
*/

bool dfs(int node, int parent, vector<int> adj[], vector<bool>& vis){
    vis[node] = true;
    for(auto v:adj[node]){
        if(!vis[v]){
            if(dfs(v,node,adj,vis))
                return true;
        }
        else if(v!=parent){
            return true;
        }
    }
    return false;
}

bool isCycle(int V, vector<int> adj[]) {
    vector<bool> vis(V);
    for(int i=0; i<V; i++){
        if(!vis[i]){
            if(dfs(i,-1,adj,vis))
                return true;
        }
    }
    return false;
}

/*
QUESTION:-
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

APPROACH:
- We can use a Breadth-First Search (BFS) traversal to find the distance of the nearest 0 for each cell.
- First, we initialize the distance matrix with -1 for all cells.
- Then, we iterate through the matrix and find all cells with the value 0. For each 0 cell found, we add it to the queue and set its distance to 0 in the distance matrix.
- Next, we perform a BFS starting from the cells with 0. During the BFS, we update the distance of each cell from the nearest 0 cell and continue the BFS until all cells are visited.
- Finally, we return the distance matrix.

COMPLEXITY ANALYSIS:
- Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. In the worst case, we may need to visit all the cells of the matrix.
- Space Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. We use additional space for the distance matrix and the queue during BFS.
*/

vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
    int m = mat.size(); 
    int n = mat[0].size();
    vector<vector<int>> dis(m, vector<int>(n, -1));
    queue<pair<int, int>> q;

    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(mat[i][j] == 0){
                dis[i][j] = 0;
                q.push({i, j});
            }
        }
    }

    vector<int> dr = {-1, 1, 0, 0};
    vector<int> dc = {0, 0, -1, 1};
    int level = 1;

    while(!q.empty()){
        int size = q.size();
        while(size--){
            auto p = q.front();
            q.pop();
            int x = p.first, y = p.second;
            for(int i = 0; i < 4; i++){
                int nx = x + dr[i], ny = y + dc[i];
                if(nx >= 0 && nx < m && ny >= 0 && ny < n && dis[nx][ny] == -1){
                    dis[nx][ny] = level;
                    q.push({nx, ny});
                }
            }
        }
        level++;
    }

    return dis;
}

/*
QUESTION:-
Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

APPROACH:
- We can use Depth-First Search (DFS) to find all regions that are surrounded by 'X'.
- First, we initialize a copy of the board called 'vis' to store the visited status of each cell.
- Then, we perform a DFS starting from all border cells that have 'O's. During the DFS, we mark all connected 'O's as visited by changing them to a special character, such as '#', in the 'vis' matrix.
- After performing DFS from border cells, all remaining '#'s in the 'vis' matrix represent regions that are not surrounded by 'X'.
- Finally, we update the original board by flipping all remaining 'O's to 'X'.

COMPLEXITY ANALYSIS:
- Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. In the worst case, we may need to visit all the cells of the matrix during DFS.
- Space Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. We use additional space for the 'vis' matrix.
*/

void dfs(int i, int j, vector<vector<char>>& vis){
    if(i >= 0 && i < vis.size() && j >= 0 && j < vis[0].size() && vis[i][j] == 'O'){
        vis[i][j] = '#';
        dfs(i + 1, j, vis);
        dfs(i - 1, j, vis);
        dfs(i, j + 1, vis);
        dfs(i, j - 1, vis);
    }
}

void solve(vector<vector<char>>& board) {
    int m = board.size(), n = board[0].size();
    vector<vector<char>> vis(board.begin(), board.end());

    // Perform DFS from border cells
    for(int i = 0; i < n; i++){
        if(vis[0][i] == 'O')
            dfs(0, i, vis);
        if(vis[m - 1][i] == 'O')
            dfs(m - 1, i, vis);
    }
    for(int i = 0; i < m; i++){
        if(vis[i][0] == 'O')
            dfs(i, 0, vis);
        if(vis[i][n - 1] == 'O')
            dfs(i, n - 1, vis);
    }

    // Update the original board
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(vis[i][j] == 'O')
                board[i][j] = 'X';
        }
    }
}

/*
QUESTION:-
You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.

A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.

Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.

APPROACH:
- We can use Depth-First Search (DFS) to mark all land cells connected to the boundary of the grid as uncountable (i.e., cells that we can walk off the boundary).
- First, we initialize a copy of the grid called 'vis' to store the visited status of each cell.
- Then, we perform DFS from all land cells located at the boundary of the grid. During the DFS, we mark all connected land cells as visited by changing their value to -1 in the 'vis' matrix.
- After performing DFS from boundary cells, all remaining land cells in the 'vis' matrix represent cells that we cannot walk off the boundary of the grid.
- Finally, we count the number of land cells in the 'vis' matrix and return the count as the result.

COMPLEXITY ANALYSIS:
- Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. In the worst case, we may need to visit all the cells of the matrix during DFS.
- Space Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. We use additional space for the 'vis' matrix.
*/

void dfs(int i, int j, vector<vector<int>>& vis){
    if(i >= 0 && i < vis.size() && j >= 0 && j < vis[0].size() && vis[i][j] == 1){
        vis[i][j] = -1;
        dfs(i + 1, j, vis);
        dfs(i - 1, j, vis);
        dfs(i, j + 1, vis);
        dfs(i, j - 1, vis);
    }
}

int numEnclaves(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> vis(grid.begin(), grid.end());

    // Perform DFS from boundary cells
    for(int i = 0; i < n; i++){
        if(vis[0][i] == 1)
            dfs(0, i, vis);
        if(vis[m - 1][i] == 1)
            dfs(m - 1, i, vis);
    }
    for(int i = 0; i < m; i++){
        if(vis[i][0] == 1)
            dfs(i, 0, vis);
        if(vis[i][n - 1] == 1)
            dfs(i, n - 1, vis);
    }

    // Count the number of land cells that are not on the boundary
    int ans = 0;
    for(auto row : vis){
        for(auto col : row){
            if(col == 1)
                ans++;
        }
    }
    return ans;
}

/*
QUESTION:
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
1. Every adjacent pair of words differs by a single letter.
2. Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
3. sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

APPROACH:
- We can model this problem as a graph where each word is a node and there is an edge between two words if they differ by a single letter.
- First, we create an adjacency list to represent the graph based on the given wordList. Two words are adjacent if they differ by one character.
- Then, we use Breadth-First Search (BFS) to find the shortest transformation sequence from beginWord to endWord.
- We start BFS from the beginWord and traverse the graph level by level, marking visited words to avoid revisiting them.
- During the BFS, if we reach the endWord, we return the length of the transformation sequence.

COMPLEXITY ANALYSIS:
- Time Complexity: O(n^2 * m), where n is the size of wordList and m is the average length of the words in wordList. In the worst case, we may need to compare every pair of words in wordList to create the adjacency list.
- Space Complexity: O(n^2), where n is the size of wordList. We use additional space for the adjacency list and the visited map.
*/

bool isAdj(string& a, string& b){
    int cnt = 0;
    for(int i = 0; i < a.size(); i++){
        if(a[i] != b[i]){
            if(cnt > 0) return false;
            cnt++;
        }
    }
    return true;
}

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_map<string, vector<string>> adj;
    wordList.push_back(beginWord);
    int n = wordList.size();

    // Create the adjacency list
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i != j && isAdj(wordList[i], wordList[j])){
                adj[wordList[i]].push_back(wordList[j]);
            }
        }
    }

    queue<string> q;
    unordered_map<string, bool> vis;
    q.push(beginWord);
    vis[beginWord] = true;
    int lvl = 1;

    // Perform BFS
    while(!q.empty()){
        int siz = q.size();
        while(siz--){
            string node = q.front();
            q.pop();
            if(node == endWord) return lvl;
            for(auto s : adj[node]){
                if(!vis[s]){
                    vis[s] = true;
                    q.push(s);
                }
            }
        }
        lvl++;
    }

    return 0;
}

/*
QUESTION:
Given a boolean 2D matrix grid of size n * m. You have to find the number of distinct islands where a group of connected 1s (horizontally or vertically) forms an island. Two islands are considered to be distinct if and only if one island is not equal to another (not rotated or reflected).

APPROACH:
- We can model this problem as a graph where each group of connected 1s forms an island.
- We can use Depth-First Search (DFS) to traverse the grid and identify each island.
- During the DFS, we keep track of the path taken to traverse each island. The path can be represented as a string, where each character in the string represents the direction of movement during the DFS (U for Up, D for Down, R for Right, and L for Left).
- We use a set to store the paths of all distinct islands. As sets store unique elements, we will have only unique paths in the set.
- Finally, we return the size of the set, which gives us the number of distinct islands.

COMPLEXITY ANALYSIS:
- Time Complexity: O(n * m), where n is the number of rows and m is the number of columns in the grid. We visit each cell at most once during the DFS.
- Space Complexity: O(n * m), where n is the number of rows and m is the number of columns in the grid. We use additional space to store the visited status of each cell and the paths of the islands in the set.
*/

void dfs(int i, int j, vector<vector<int>>& grid, string& path, vector<vector<bool>>& vis){
    if(i >= 0 && i < grid.size() && j >= 0 && j < grid[0].size() && grid[i][j] == 1 && !vis[i][j]){
        vis[i][j] = true;
        dfs(i + 1, j, grid, path += "U", vis);
        dfs(i - 1, j, grid, path += "D", vis);
        dfs(i, j + 1, grid, path += "R", vis);
        dfs(i, j - 1, grid, path += "L", vis);
    }  
}

int countDistinctIslands(vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<bool>> vis(n, vector<bool>(m));

    unordered_set<string> st;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(grid[i][j] == 1 && !vis[i][j]){
                string path = "";
                dfs(i, j, grid, path, vis);
                st.insert(path);
            }
        }
    }

    return st.size();
}

/*
QUESTION:
There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:
1. There are no self-edges (graph[u] does not contain u).
2. There are no parallel edges (graph[u] does not contain duplicate values).
3. If v is in graph[u], then u is in graph[v] (the graph is undirected).
The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

APPROACH:
- We can use Depth-First Search (DFS) to color the nodes in the graph such that we can partition them into two sets A and B.
- While performing the DFS, we use two colors: 1 and -1 to color the nodes. We start by coloring the first node with color 1.
- For each uncolored node, we perform DFS and color its neighbors with the opposite color.
- If we encounter a neighbor with the same color as the current node, the graph is not bipartite, and we return false.
- If the DFS completes without any conflicts, we return true, indicating that the graph is bipartite.

COMPLEXITY ANALYSIS:
- Time Complexity: O(V + E), where V is the number of nodes (vertices) in the graph, and E is the number of edges in the graph. We visit each node and each edge exactly once during the DFS.
- Space Complexity: O(V), where V is the number of nodes (vertices) in the graph. We use additional space to store the colors of the nodes.
*/

bool dfs(int node, int color, vector<vector<int>>& adj, vector<int>& vis){
    vis[node] = color;
    for(auto v : adj[node]){
        if(!vis[v] && !dfs(v, -color, adj, vis)){
            return false;
        }
        if(vis[v] == color){
            return false;
        }
    }
    return true;
}

bool isBipartite(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> vis(n);
    for(int i = 0; i < n; i++){
        if(!vis[i] && !dfs(i, 1, graph, vis)){
            return false;
        }
    }
    return true;
}

/*
QUESTION:
Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, check whether it contains any cycle or not.

APPROACH:
- To check for cycles in a directed graph, we can use Depth-First Search (DFS) with backtracking.
- During the DFS, we maintain a visited array to keep track of nodes that have been visited.
- We perform DFS from each unvisited node to explore the graph and check for cycles.
- If we encounter a node that is already visited in the current DFS traversal, it means we have found a cycle, and we return true.
- If we complete the DFS for all nodes without finding any cycle, we return false.

COMPLEXITY ANALYSIS:
- Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. We visit each node and each edge exactly once during the DFS.
- Space Complexity: O(V), where V is the number of vertices (nodes) in the graph. We use additional space to store the visited status of the nodes.
*/

bool dfs(int node, vector<int> adj[], vector<bool>& vis){
    vis[node] = true;
    for(auto v : adj[node]){
        if(!vis[v] && dfs(v, adj, vis)){
            return true;
        }
        else if(vis[v]){
            return true;
        }
    }
    vis[node] = false;
    return false;
}

bool isCyclic(vector<vector<int>>& edges, int v, int e)
{
    vector<int> adj[v];
    for(auto it : edges){
        adj[it[0]].push_back(it[1]);
    }
    vector<bool> vis(v);
    for(int i = 0; i < v; i++){
        if(!vis[i] && dfs(i, adj, vis)){
            return true;
        }
    }
    return false;
}

/*
QUESTION:
Given a DAG (directed acyclic graph), print the Topological sorting of a given graph.

APPROACH:
- Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u -> v, vertex u comes before v in the ordering.
- To find the topological sorting, we can use Depth-First Search (DFS) with backtracking.
- We perform DFS starting from each unvisited node, and as we finish exploring a node and backtrack, we add it to the front of the topological sorting order.

COMPLEXITY ANALYSIS:
- Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. We visit each node and each edge exactly once during the DFS.
- Space Complexity: O(V), where V is the number of vertices (nodes) in the graph. We use additional space to store the visited status of the nodes and the topological sorting order.
*/

bool dfs(int node, vector<int> adj[], vector<bool>& vis, vector<int>& ans){
    vis[node] = true;
    for(auto v : adj[node]){
        if(!vis[v]){
            dfs(v, adj, vis, st);
        }
    }
    ans.push_back(node);
}

vector<int> topologicalSort(vector<vector<int>>& graph, int edges, int nodes) {
    vector<int> adj[nodes];
    for(auto it : graph){
        adj[it[0]].push_back(it[1]);
    }
    vector<bool> vis(nodes);
    vector<int> ans;
    for(int i = 0; i < nodes; i++){
        if(!vis[i]){
            dfs(i, adj, vis, ans);
        }
    }

    reverse(ans.begin(),ans.end());

    return ans;
}

/*
QUESTION:
Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, check whether it contains any cycle or not.

APPROACH:
- We can use Topological Sorting to check if a directed graph contains a cycle or not.
- If a directed graph is a DAG (Directed Acyclic Graph), it means it does not contain any cycle.
- So, to check for a cycle, we perform a variation of Topological Sorting using Kahn's algorithm, which is based on the concept of indegree.
- If there is no cycle in the graph, we can always find a node with an indegree of 0 (no incoming edges) and remove it along with its outgoing edges.
- We keep repeating this process, and if at any point we are unable to find a node with an indegree of 0, it means there is a cycle in the graph.

COMPLEXITY ANALYSIS:
- Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. We perform a BFS-like traversal of all nodes and edges.
- Space Complexity: O(V), where V is the number of vertices (nodes) in the graph. We use additional space to store the indegree of each node and the queue for BFS.
*/

bool isCyclic(int V, vector<int> adj[]) {
    vector<int> indeg(V, 0);

    // Calculate the indegree of each node
    for (int i = 0; i < V; i++) {
        for (auto it : adj[i]) {
            indeg[it]++;
        }
    }

    queue<int> q;

    // Find nodes with indegree 0 and add them to the queue
    for (int i = 0; i < V; i++) {
        if (indeg[i] == 0) {
            q.push(i);
        }
    }

    int cnt = 0;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cnt++;

        // Remove the node and its outgoing edges
        for (auto i : adj[node]) {
            indeg[i]--;
            if (indeg[i] == 0) {
                q.push(i);
            }
        }
    }

    // If the count of removed nodes is not equal to the total number of nodes, there is a cycle
    return !(cnt == V);
}

/*
QUESTION:
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

Return true if you can finish all courses. Otherwise, return false.

APPROACH:
- We can model the problem as a directed graph, where each course is a node, and a prerequisite pair [ai, bi] indicates a directed edge from course bi to course ai.
- To check if we can finish all courses, we need to ensure that the directed graph is a DAG (Directed Acyclic Graph) with no cycles.
- If there are cycles in the graph, it means there is a circular dependency between courses, and we cannot finish all courses in such cases.
- To check for cycles, we can use Kahn's algorithm for Topological Sorting.
- If we can perform a successful Topological Sort (i.e., there is no cycle), then it means we can finish all courses.

COMPLEXITY ANALYSIS:
- Time Complexity: O(N + E), where N is the number of courses (nodes) and E is the number of prerequisites (edges) in the graph. We perform a BFS-like traversal of all nodes and edges.
- Space Complexity: O(N + E), where N is the number of courses (nodes) and E is the number of prerequisites (edges) in the graph. We use additional space to store the adjacency list and indegree of each node.
*/

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> indeg(numCourses, 0);
    vector<vector<int>> adj(numCourses);

    // Calculate the indegree of each course and build the adjacency list
    for (auto it : prerequisites) {
        indeg[it[0]]++;
        adj[it[1]].push_back(it[0]);
    }

    queue<int> q;

    // Find courses with indegree 0 and add them to the queue
    for (int i = 0; i < numCourses; i++) {
        if (indeg[i] == 0) {
            q.push(i);
        }
    }

    int cnt = 0;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cnt++;

        // Remove the course and its outgoing edges
        for (auto v : adj[node]) {
            indeg[v]--;
            if (indeg[v] == 0) {
                q.push(v);
            }
        }
    }

    // If the count of finished courses is equal to the total number of courses, return true
    return cnt == numCourses;
}

/*
QUESTION:
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

APPROACH:
- We can model the problem as a directed graph, where each course is a node, and a prerequisite pair [ai, bi] indicates a directed edge from course bi to course ai.
- To find the course ordering, we can use Kahn's algorithm for Topological Sorting.
- If we can perform a successful Topological Sort, it means we can finish all courses, and the order in which we pop the nodes from the queue will give us the correct course order.
- If there is a cycle in the graph (i.e., it is not possible to finish all courses), the algorithm will not be able to remove all nodes with indegree 0, and we will not get a valid course ordering.

COMPLEXITY ANALYSIS:
- Time Complexity: O(N + E), where N is the number of courses (nodes) and E is the number of prerequisites (edges) in the graph. We perform a BFS-like traversal of all nodes and edges.
- Space Complexity: O(N + E), where N is the number of courses (nodes) and E is the number of prerequisites (edges) in the graph. We use additional space to store the adjacency list and indegree of each node.
*/

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> indeg(numCourses, 0);
    vector<vector<int>> adj(numCourses);

    // Calculate the indegree of each course and build the adjacency list
    for (auto it : prerequisites) {
        indeg[it[0]]++;
        adj[it[1]].push_back(it[0]);
    }

    queue<int> q;

    // Find courses with indegree 0 and add them to the queue
    for (int i = 0; i < numCourses; i++) {
        if (indeg[i] == 0) {
            q.push(i);
        }
    }

    vector<int> courseOrder;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        courseOrder.push_back(node);

        // Remove the course and its outgoing edges
        for (auto v : adj[node]) {
            indeg[v]--;
            if (indeg[v] == 0) {
                q.push(v);
            }
        }
    }

    // If the size of the course order is equal to the total number of courses, return the order
    if (courseOrder.size() == numCourses) {
        return courseOrder;
    }

    // If not all courses are covered, return an empty array
    return {};
}

/*
QUESTION:
There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

APPROACH:
- We are given a directed graph, and we need to find all the safe nodes.
- A node is safe if every possible path starting from that node leads to a terminal node (or another safe node).
- To solve this, we can use a reverse graph approach along with a topological sorting method.
- We create a reverse adjacency list, where revadj[i] contains all the nodes from which there is a directed edge to node i (i.e., nodes that have an edge towards node i).
- We also keep track of the outdegree of each node, which represents the number of outgoing edges from that node.
- We then start with nodes that have an outdegree of 0 (i.e., terminal nodes) and perform a BFS-like traversal.
- During the traversal, we keep reducing the outdegree of the nodes from which there is a directed edge to the current node.
- If a node's outdegree becomes 0 during the traversal, we add it to the queue for further processing.
- All the nodes that become terminal nodes during the traversal are safe nodes.

COMPLEXITY ANALYSIS:
- Time Complexity: O(N + E), where N is the number of nodes, and E is the number of edges in the graph. We perform a BFS-like traversal of all nodes and edges.
- Space Complexity: O(N + E), where N is the number of nodes, and E is the number of edges in the graph. We use additional space to store the reverse adjacency list and outdegree of each node.
*/

vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
    int n = graph.size();
    // Creating reverse adjacency list and outdegree array
    vector<int> revadj[n];
    vector<int> outdeg(n);
    for (int i = 0; i < n; i++) {
        outdeg[i] += graph[i].size();
        for (auto j : graph[i]) {
            revadj[j].push_back(i);
        }
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (outdeg[i] == 0) q.push(i);
    }

    vector<int> ans;

    while (!q.empty()) {
        int siz = q.size();
        while (siz--) {
            int node = q.front();
            q.pop();
            ans.push_back(node);

            // Reduce outdegree of the nodes from which there is a directed edge to the current node
            for (auto v : revadj[node]) {
                outdeg[v]--;
                if (outdeg[v] == 0) {
                    q.push(v);
                }
            }
        }
    }

    // Sort the safe nodes in ascending order
    sort(ans.begin(), ans.end());
    return ans;
}