import java.util.*;
import org.w3c.dom.Node;
public class graph {
// Function to return Breadth First Traversal of given graph.
public static ArrayList<Integer> bfsOfGraph(int numNodes, ArrayList<ArrayList<Integer>> adj) {
ArrayList < Integer > bfs = new ArrayList < > (); // stores ans
boolean vis[] = new boolean[numNodes + 1];
Queue < Integer > q = new LinkedList < > ();
// keep any node from where you want to start your bfs
q.add(1); // keep value of node here, if your node has 0 then you should keep it
vis[1] = true;
while (!q.isEmpty()) {
int levelSize = q.size(); // Number of nodes at the current level
for (int i = 0; i < levelSize; i++) {
Integer node = q.poll();
bfs.add(node);
for (Integer it : adj.get(node)) {
if (!vis[it]) {
vis[it] = true;
q.add(it);
}
}
}
bfs.add(-1); // Add a marker (-1) to separate levels
}
return bfs;
}
// Function to return a list containing the DFS traversal of the graph.
public static void dfs(int node, boolean vis[], ArrayList<ArrayList<Integer>> adj,
ArrayList<Integer> ls) {
//marking current node as visited
vis[node] = true;
ls.add(node);
//getting neighbour nodes
for(Integer it: adj.get(node)) {
if(vis[it] == false) {
dfs(it, vis, adj, ls);
}
}
}
public static ArrayList<Integer> dfsOfGraph(int numNodes, ArrayList<ArrayList<Integer>> adj) {
//boolean array to keep track of visited vertices
boolean vis[] = new boolean[numNodes+1];
vis[1] = true;
ArrayList<Integer> ls = new ArrayList<>();
dfs(1, vis, adj, ls);
return ls;
}
// Total number of provinces in given graph
public static void dfs(int node,
ArrayList<ArrayList<Integer>> adjLs ,
int vis[]) {
vis[node] = 1;
for(Integer it: adjLs.get(node)) {
if(vis[it] == 0) {
dfs(it, adjLs, vis);
}
}
}
public static int numProvinces(ArrayList<ArrayList<Integer>> adj, int V) {
int vis[] = new int[V + 1]; // +1
int cnt = 0;
for (int i = 1; i < V+1; i++) { // Start from vertex 1 (assuming 1-based indexing)
if (vis[i] == 0) {
cnt++;
dfs(i, adj, vis);
}
}
return cnt;
}
// Count number of islands
public static class Pair {
public int first;
public int second;
public Pair(int first, int second) {
this.first = first;
this.second = second;
}
}
public static void bfs(int ro, int co, int[][] vis, char[][] grid) {
vis[ro][co] = 1;
Queue<Pair> q = new LinkedList<Pair>();
q.add(new Pair(ro, co));
int n = grid.length;
int m = grid[0].length;
// until the queue becomes empty
while(!q.isEmpty()) {
int row = q.peek().first;
int col = q.peek().second;
q.remove();
// traverse in the neighbours and mark them if its a land
for(int delrow = -1; delrow<=1;delrow++) {
for(int delcol = -1; delcol <= 1; delcol++) {
int nrow = row + delrow;
int ncol = col + delcol;
// check if neighbour row and column is valid, and is an unvisited land
if(nrow >= 0 && nrow < n && ncol >= 0 && ncol < m
&& grid[nrow][ncol] == '1' && vis[nrow][ncol] == 0) {
vis[nrow][ncol] = 1;
q.add(new Pair(nrow, ncol));
}
}
}
}
}
// Function to find the number of islands.
public static int numIslands(char[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][] vis = new int[n][m];
int cnt = 0;
for(int row = 0; row < n ; row++) {
for(int col = 0; col < m ;col++) {
// if not visited and is a land
if(vis[row][col] == 0 && grid[row][col] == '1') {
cnt++;
bfs(row, col, vis, grid);
}
}
}
return cnt;
}
// Flood-Fill Algorithm
public static void dfs_floodfill(int row, int col,
int[][] ans,
int[][] image,
int newColor, int delRow[], int delCol[],
int iniColor) {
// color with new color
ans[row][col] = newColor;
int n = image.length;
int m = image[0].length;
// there are exactly 4 neighbours
for(int i = 0;i<4;i++) {
int nrow = row + delRow[i];
int ncol = col + delCol[i];
// check for valid coordinate
// then check for same initial color and unvisited pixel
if(nrow>=0 && nrow<n && ncol>=0 && ncol < m &&
image[nrow][ncol] == iniColor && ans[nrow][ncol] != newColor) {
dfs_floodfill(nrow, ncol, ans, image, newColor, delRow, delCol, iniColor);
}
}
}
public static int[][] floodFill(int[][] image, int sr, int sc, int newColor)
{
// get initial color
int iniColor = image[sr][sc];
int[][] ans = image;
// delta row and delta column for neighbours
int delRow[] = {-1, 0, +1, 0};
int delCol[] = {0, +1, 0, -1};
dfs_floodfill(sr, sc, ans, image, newColor, delRow, delCol, iniColor);
return ans;
}
// Rotten oranges
public static class Pair_rottenOranges {
int row;
int col;
int tm;
Pair_rottenOranges(int _row, int _col, int _tm) {
this.row = _row;
this.col = _col;
this.tm = _tm;
}
}
//Function to find minimum time required to rot all oranges.
public static int orangesRotting(int[][] grid) {
// figure out the grid size
int n = grid.length;
int m = grid[0].length;
// n x m
Queue < Pair_rottenOranges > q = new LinkedList < > ();
// n x m
int[][] vis = new int[n][m];
int cntFresh = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// if cell contains rotten orange
if (grid[i][j] == 2) {
q.add(new Pair_rottenOranges(i, j, 0));
// mark as visited (rotten) in visited array
vis[i][j] = 2;
}
// if not rotten
else {
vis[i][j] = 0;
}
// count fresh oranges
if (grid[i][j] == 1) cntFresh++;
}
}
int tm = 0;
// delta row and delta column
int drow[] = {-1, 0, +1, 0};
int dcol[] = {0, 1, 0, -1};
int cnt = 0;
// until the queue becomes empty
while (!q.isEmpty()) {
int r = q.peek().row;
int c = q.peek().col;
int t = q.peek().tm;
tm = Math.max(tm, t);
q.remove();
// exactly 4 neighbours
for (int i = 0; i < 4; i++) {
int nrow = r + drow[i];
int ncol = c + dcol[i];
// check for valid coordinates and
// then for unvisited fresh orange
if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < m &&
vis[nrow][ncol] == 0 && grid[nrow][ncol] == 1) {
// push in queue with timer increased
q.add(new Pair_rottenOranges(nrow, ncol, t + 1));
// mark as rotten
vis[nrow][ncol] = 2;
cnt++;
}
}
}
// if all oranges are not rotten
if (cnt != cntFresh) return -1;
return tm;
}
// To detect cycle in graph using bfs
public static class Node {
int first;
int second;
public Node(int first, int second) {
this.first = first;
this.second = second;
}
}
public static boolean checkForCycle(ArrayList<ArrayList<Integer>> adj, int s,
boolean vis[], int parent[])
{
Queue<Node> q = new LinkedList<>(); //BFS
q.add(new Node(s, -1));
vis[s] =true;
// until the queue is empty
while(!q.isEmpty())
{
// source node and its parent node
int node = q.peek().first;
int par = q.peek().second;
q.remove();
// go to all the adjacent nodes
for(Integer it: adj.get(node))
{
if(vis[it]==false)
{
q.add(new Node(it, node));
vis[it] = true;
}
// if adjacent node is visited and is not its own parent node
else if(par != it) return true;
}
}
return false;
}
// function to detect cycle in an undirected graph
public static boolean isCycle(int numNodes, ArrayList<ArrayList<Integer>> adj)
{
boolean vis[] = new boolean[numNodes+1];
Arrays.fill(vis,false);
int parent[] = new int[numNodes+1];
Arrays.fill(parent,-1);
for(int i=1;i<numNodes+1;i++)
if(vis[i]==false)
if(checkForCycle(adj, i,vis, parent))
return true;
return false;
}
// detect cycle in graph via dfs
public static boolean dfs_cycle(int node, int parent, int vis[], ArrayList<ArrayList<Integer>>
adj) {
vis[node] = 1;
// go to all adjacent nodes
for(int adjacentNode: adj.get(node)) {
if(vis[adjacentNode]==0) {
if(dfs_cycle(adjacentNode, node, vis, adj) == true)
return true;
}
// if adjacent node is visited and is not its own parent node
else if(adjacentNode != parent) return true;
}
return false;
}
// Function to detect cycle in an undirected graph.
public static boolean isCycle_dfs(int numNode, ArrayList<ArrayList<Integer>> adj) {
int vis[] = new int[numNode+1];
for(int i = 1;i<numNode+1;i++) {
if(vis[i] == 0) {
if(dfs_cycle(i, -1, vis, adj) == true) return true;
}
}
return false;
}
// Distance of nearest cell having 1 | 0/1 Matrix
//Function to find distance of nearest 1 in the grid for each cell.
public static class Node_dist {
int first;
int second;
int third;
Node_dist(int _first, int _second, int _third) {
this.first = _first;
this.second = _second;
this.third = _third;
}
}
public static int[][] nearest(int[][] grid)
{
int n = grid.length;
int m = grid[0].length;
// visited and distance matrix
int vis[][] = new int[n][m];
int dist[][] = new int[n][m];
// <coordinates, steps>
Queue<Node_dist> q = new LinkedList<Node_dist>();
// traverse the matrix
for(int i = 0;i<n;i++) {
for(int j = 0;j<m;j++) {
// start BFS if cell contains 1
if(grid[i][j] == 1) {
q.add(new Node_dist(i, j, 0));
vis[i][j] = 1;
}
else {
// mark unvisted
vis[i][j] = 0;
}
}
}
int delrow[] = {-1, 0, +1, 0};
int delcol[] = {0, +1, 0, -1};
// n x m x 4
// traverse till queue becomes empty
while(!q.isEmpty()) {
int row = q.peek().first;
int col = q.peek().second;
int steps = q.peek().third;
q.remove();
dist[row][col] = steps;
// for all 4 neighbours
for(int i = 0;i<4;i++) {
int nrow = row + delrow[i];
int ncol = col + delcol[i];
// check for valid unvisited cell
if(nrow >= 0 && nrow < n && ncol >= 0 && ncol < m
&& vis[nrow][ncol] == 0) {
vis[nrow][ncol] = 1;
q.add(new Node_dist(nrow, ncol, steps+1));
}
}
}
// return distance matrix
return dist;
}
// Surrounded regions replace '0s' with 'X'
static void dfs(int row, int col,int vis[][],
char mat[][], int delrow[], int delcol[]) {
vis[row][col] = 1;
int n = mat.length;
int m = mat[0].length;
// check for top, right, bottom, left
for(int i = 0;i<4;i++) {
int nrow = row + delrow[i];
int ncol = col + delcol[i];
// check for valid coordinates and unvisited Os
if(nrow >=0 && nrow <n && ncol >= 0 && ncol < m
&& vis[nrow][ncol] == 0 && mat[nrow][ncol] == 'O') {
dfs(nrow, ncol, vis, mat, delrow, delcol);
}
}
}
static char[][] fill(int n, int m, char mat[][])
{
int delrow[] = {-1, 0, +1, 0};
int delcol[] = {0, 1, 0, -1};
int vis[][] = new int[n][m];
// traverse first row and last row
for(int j = 0 ; j<m;j++) {
// check for unvisited Os in the boundary rws
// first row
if(vis[0][j] == 0 && mat[0][j] == 'O') {
dfs(0, j, vis, mat, delrow, delcol);
}
// last row
if(vis[n-1][j] == 0 && mat[n-1][j] == 'O') {
dfs(n-1,j,vis,mat, delrow, delcol);
}
}
for(int i = 0;i<n;i++) {
// check for unvisited Os in the boundary columns
// first column
if(vis[i][0] == 0 && mat[i][0] == 'O') {
dfs(i, 0, vis, mat, delrow, delcol);
}
// last column
if(vis[i][m-1] == 0 && mat[i][m-1] == 'O') {
dfs(i, m-1, vis, mat, delrow, delcol);
}
}
// if unvisited O then convert to X
for(int i = 0;i<n;i++) {
for(int j= 0 ;j<m;j++) {
if(vis[i][j] == 0 && mat[i][j] == 'O')
mat[i][j] = 'X';
}
}
return mat;
}
// Number of Enclaves
public static int numberOfEnclaves(int[][] grid) {
Queue<Pair> q = new LinkedList<Pair>();
int n = grid.length;
int m = grid[0].length;
int vis[][] = new int[n][m];
// traverse boundary elements
for(int i = 0;i<n;i++) {
for(int j = 0;j<m;j++) {
// first row, first col, last row, last col
if(i == 0 || j == 0 || i == n-1 || j == m-1) {
// if it is a land then store it in queue
if(grid[i][j] == 1) {
q.add(new Pair(i, j));
vis[i][j] = 1;
}
}
}
}
int delrow[] = {-1, 0, +1, 0};
int delcol[] = {0, +1, +0, -1};
while(!q.isEmpty()) {
int row = q.peek().first;
int col = q.peek().second;
q.remove();
// traverses all 4 directions
for(int i = 0;i<4;i++) {
int nrow = row + delrow[i];
int ncol = col + delcol[i];
// check for valid coordinates and for land cell
if(nrow >=0 && nrow <n && ncol >=0 && ncol < m
&& vis[nrow][ncol] == 0 && grid[nrow][ncol] == 1) {
q.add(new Pair(nrow, ncol));
vis[nrow][ncol] = 1;
}
}
}
int cnt = 0;
for(int i = 0;i<n;i++) {
for(int j = 0;j<m;j++) {
// check for unvisited land cell
if(grid[i][j] == 1 & vis[i][j] == 0)
cnt++;
}
}
return cnt;
}
// Number of distinct islands
public static void dfs_islands(int row, int col, int[][] vis,
int[][] grid, ArrayList < String > vec, int row0, int col0) {
// mark the cell as visited
vis[row][col] = 1;
// coordinates - base coordinates
vec.add(toString(row - row0, col - col0));
int n = grid.length;
int m = grid[0].length;
// delta row and delta column
int delrow[] = {-1, 0, +1, 0};
int delcol[] = {0, -1, 0, +1};
// traverse all 4 neighbours
for (int i = 0; i < 4; i++) {
int nrow = row + delrow[i];
int ncol = col + delcol[i];
// check for valid unvisited land neighbour coordinates
if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < m &&
vis[nrow][ncol] == 0 && grid[nrow][ncol] == 1) {
dfs_islands(nrow, ncol, vis, grid, vec, row0, col0);
}
}
}
public static String toString(int r, int c) {
return Integer.toString(r) + " " + Integer.toString(c);
}
public static int countDistinctIslands(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int vis[][] = new int[n][m];
HashSet < ArrayList < String >> st = new HashSet < > ();
// traverse the grid
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// if not visited and is a land cell
if (vis[i][j] == 0 && grid[i][j] == 1) {
ArrayList < String > vec = new ArrayList < > ();
dfs_islands(i, j, vis, grid, vec, i, j);
// store it in HashSet
st.add(vec);
}
}
}
return st.size();
}
// Bipartite Graph using bfs
public static boolean check(int start, int numNodes,
ArrayList<ArrayList<Integer>>adj, int color[]) {
Queue<Integer> q = new LinkedList<Integer>();
q.add(start);
color[start] = 0;
while(!q.isEmpty()) {
int node = q.peek();
q.remove();
for(int it : adj.get(node)) {
// if the adjacent node is yet not colored
// you will give the opposite color of the node
if(color[it] == -1) {
color[it] = 1 - color[node];
q.add(it);
}
// is the adjacent guy having the same color
// someone did color it on some other path
else if(color[it] == color[node]) {
return false;
}
}
}
return true;
}
public static boolean isBipartite(int numNodes, ArrayList<ArrayList<Integer>>adj)
{
int color[] = new int[numNodes+1];
for(int i = 1;i<numNodes+1;i++) color[i] = -1;
for(int i = 1;i<numNodes+1;i++) {
if(color[i] == -1) {
if(check(i, numNodes, adj, color) == false) {
return false;
}
}
}
return true;
}
// Bipartite Graph(using DFS)
public static boolean dfs_bipartite(int node, int col, int color[],
ArrayList<ArrayList<Integer>>adj) {
color[node] = col;
// traverse adjacent nodes
for(int it : adj.get(node)) {
// if uncoloured
if(color[it] == -1) {
if(dfs_bipartite(it, 1 - col, color, adj) == false) return false;
}
// if previously coloured and have the same colour
else if(color[it] == col) {
return false;
}
}
return true;
}
public static boolean isBipartite_dfs(int numNodes, ArrayList<ArrayList<Integer>>adj)
{
int color[] = new int[numNodes + 1];
for(int i = 1;i<numNodes+1;i++) color[i] = -1;
// for connected components
for(int i = 1;i<numNodes+1;i++) {
if(color[i] == -1) {
if(dfs_bipartite(i, 0, color, adj) == false) return false;
}
}
return true;
}
// Detect cycle in a directed graph (using DFS)
public static boolean dfsCheck_directedG(int node, ArrayList<ArrayList<Integer>> adj, int vis[], int pathVis[]) {
vis[node] = 1;
pathVis[node] = 1;
// traverse for adjacent nodes
for(int it : adj.get(node)) {
// when the node is not visited
if(vis[it] == 0) {
if(dfsCheck_directedG(it, adj, vis, pathVis) == true)
return true;
}
// if the node has been previously visited
// but it has to be visited on the same path
else if(pathVis[it] == 1) {
return true;
}
}
pathVis[node] = 0;
return false;
}
// Function to detect cycle in a directed graph via DFS
public static boolean isCyclic_directedG(int numNodes, ArrayList<ArrayList<Integer>> adj) {
int vis[] = new int[numNodes+1];
int pathVis[] = new int[numNodes+1];
for(int i = 1;i<numNodes+1;i++) {
if(vis[i] == 0) {
if(dfsCheck_directedG(i, adj, vis, pathVis) == true) return true;
}
}
return false;
}
// Find eventual safe states
public static boolean dfsCheck_safeStates(int node, ArrayList<ArrayList<Integer>> adj, int vis[],
int pathVis[], int check[]) {
vis[node] = 1;
pathVis[node] = 1;
check[node] = 0;
// traverse for adjacent nodes
for (int it : adj.get(node)) {
// when the node is not visited
if (vis[it] == 0) {
if (dfsCheck_safeStates(it, adj, vis, pathVis, check) == true)
return true;
}
// if the node has been previously visited
// but it has to be visited on the same path
else if (pathVis[it] == 1) {
return true;
}
}
check[node] = 1;
pathVis[node] = 0;
return false;
}
public static List<Integer> eventualSafeNodes(int numNodes, ArrayList<ArrayList<Integer>> adj) {
int vis[] = new int[numNodes+1];
int pathVis[] = new int[numNodes+1];
int check[] = new int[numNodes+1];
for (int i = 1; i < numNodes+1; i++) {
if (vis[i] == 0) {
dfsCheck_safeStates(i, adj, vis, pathVis, check);
}
}
ArrayList<Integer> safeNodes = new ArrayList<>();
for (int i = 1; i < numNodes+1; i++) {
if (check[i] == 1)
safeNodes.add(i);
}
return safeNodes;
}
// Topological Sort
public static void dfs_topo(int node, int vis[], Stack<Integer> st,
ArrayList<ArrayList<Integer>> adj) {
vis[node] = 1;
for (int it : adj.get(node)) {
if (vis[it] == 0)
dfs_topo(it, vis, st, adj);
}
st.push(node);
}
// Function to return list containing vertices in Topological order.
public static int[] topoSort(int numNodes, ArrayList<ArrayList<Integer>> adj) {
int vis[] = new int[numNodes+1];
Stack<Integer> st = new Stack<Integer>();
for (int i = 1; i < numNodes+1; i++) {
if (vis[i] == 0) {
dfs_topo(i, vis, st, adj);
}
}
int ans[] = new int[numNodes];
int i = 0;
while (!st.isEmpty()) {
ans[i++] = st.peek();
st.pop();
}
return ans;
}
// Topological Sort using Kanh's Algorithm
// Function to return list containing vertices in Topological order.
public static int[] topoSort_Kanhs(int numNodes, ArrayList<ArrayList<Integer>> adj) {
int indegree[] = new int[numNodes+1];
for (int i = 1; i < numNodes+1; i++) {
for (int it : adj.get(i)) {
indegree[it]++;
}
}
Queue<Integer> q = new LinkedList<Integer>();
for (int i = 1; i < numNodes+1; i++) {
if (indegree[i] == 0) {
q.add(i);
}
}
int topo[] = new int[numNodes];
int i = 0;
while (!q.isEmpty()) {
int node = q.peek();
q.remove();
topo[i++] = node;
// node is in your topo sort
// so please remove it from the indegree
for (int it : adj.get(node)) {
indegree[it]--;
if (indegree[it] == 0) {
q.add(it);
}
}
}
return topo;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Input the number of nodes.
System.out.print("Enter the number of nodes: ");
int numNodes = scanner.nextInt();
// Create an adjacency list.
ArrayList<ArrayList<Integer>> adjList = new ArrayList<>(numNodes);
for (int i = 0; i < numNodes + 1; i++) { // numNodes + 2 only if remove empty zero index
adjList.add(new ArrayList<>());
}
// Input the number of edges.
System.out.print("Enter the number of edges: ");
int numEdges = scanner.nextInt();
// Input the edges (connections between nodes).
System.out.println("Enter the edges (startNode endNode):");
for (int i = 0; i < numEdges; i++) {
int startNode = scanner.nextInt();
int endNode = scanner.nextInt();
// Add an edge from startNode to endNode (for directed graph).
adjList.get(startNode).add(endNode);
// For undirected graph, add the reverse edge as well.
// adjList.get(endNode).add(startNode); // Uncomment this line for an undirected graph.
}
// Print the adjacency list.
System.out.println("Adjacency List:");
for (int i = 1; i < numNodes + 1; i++) { // if start from zero then empty list will also be seen
System.out.print(i + " -> ");
for (int neighbor : adjList.get(i)) {
System.out.print(neighbor + " ");
}
System.out.println();
}
// BFS of graph
System.out.println("The bfs of the given graph is:");
ArrayList<Integer> bfsResult = bfsOfGraph(numNodes, adjList);
for (Integer node : bfsResult) {
if (node == -1) {
System.out.println(); // Print a newline for each level
} else {
System.out.print(node + " ");
}
}
// DFS of graph
System.out.println("The dfs of the given graph is:");
System.out.println(dfsOfGraph(numNodes, adjList));
// number of provinces
System.out.println("The total number of provinces in your graph is: "+numProvinces(adjList, numNodes));
// count number of islands from the given graph(grid)--> 2D Matrix
char[][] grid = {
{'0', '1', '1', '1', '0', '0', '0'},
{'0', '0', '1', '1', '0', '1', '0'}
};
System.out.println("The total number of island in the grid is: "+numIslands(grid));
// Flood Fill algorithm
System.out.println("The matix after flood fill is below:");
int[][] image = {
{1,1,1},
{1,1,0},
{1,0,1}
};
// sr = 1, sc = 1, newColor = 2
int[][] ans = floodFill(image, 1, 1, 2);
for(int i = 0; i < ans.length; i++){
for(int j = 0; j < ans[i].length; j++)
System.out.print(ans[i][j] + " ");
System.out.println();
}
// Rotten Oranges
int[][] grid_rottenOranges = {{0,1,2},{0,1,1},{2,1,1}};
System.out.println("The minimum time required to rot all the oranges are: "+orangesRotting(grid_rottenOranges));
// Cycle in graph via BFS
System.out.println("Is the graph contain cycle(via BFS)? "+isCycle(numNodes,adjList));
// Cycle in graph via DFS
System.out.println("Is the graph contain cycle(via DFS)? "+isCycle_dfs(numNodes,adjList));
// Distance of nearest cell having 1
int[][] grid_dist = {
{0,1,1,0},
{1,1,0,0},
{0,0,1,1}
};
int ans_dist[][] = nearest(grid_dist);
System.out.println("The nearest distance matrix is as below:");
for(int i = 0; i < ans_dist.length; i++){
for(int j = 0; j < ans_dist[i].length; j++){
System.out.print(ans_dist[i][j] + " ");
}
System.out.println();
}
// Surrounded region replace O with X
System.out.println("Surrounded region matrix after is as below:");
char mat[][] = {
{'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X'},
{'X', 'O', 'O', 'X'},
{'X', 'O', 'X', 'X'},
{'X', 'X', 'O', 'O'}};
// n = 5, m = 4
char[][] ans_surround = fill(5, 4, mat);
for(int i = 0;i < 5;i++) {
for(int j = 0;j < 4;j++) {
System.out.print(ans_surround[i][j] + " ");
}
System.out.println();
}
// Number of Enclaves
int grid_enclaves[][] = {
{0, 0, 0, 0},
{1, 0, 1, 0},
{0, 1, 1, 0},
{0, 0, 0, 0}};
int ans_enclaves = numberOfEnclaves(grid_enclaves);
System.out.println("The total number of enclaves are: "+ans_enclaves);
// Number of distinct islands
int grid_islands[][] = {
{1, 1, 0, 1, 1},
{1, 0, 0, 0, 0},
{0, 0, 0, 0, 1},
{1, 1, 0, 1, 1}};
int ans_islands = countDistinctIslands(grid_islands);
System.out.println("The total number of distinct islands are: "+ans_islands);
// Bipartite Graph using bfs
System.out.println("Is the graph Bipartite(using bfs): "+isBipartite(numNodes, adjList));
// Bipartite Graph using dfs
System.out.println("Is the graph Bipartite(using dfs): "+isBipartite_dfs(numNodes, adjList));
// CYCLE DTECTION IN DIRECTED GRAPH VIA DFS
System.out.println("Is the directed graph contains cycle: "+isCyclic_directedG(numNodes,adjList));
// Eventual safe nodes
System.out.println("The eventual safe nodes are: "+eventualSafeNodes(numNodes,adjList));
// Topological Sort
System.out.println("The topological sort of the graph is:");
int[] ans_topo = topoSort(numNodes, adjList);
for (int node : ans_topo) {
System.out.print(node + " ");
}
System.out.println("");
// Topological Sort using Kanh's Algorithm
int[] ans_topo_kanhs = topoSort(numNodes, adjList);
System.out.println("The topological sort of the graph using Kanh's Algorithm is:");
for (int node : ans_topo_kanhs) {
System.out.print(node + " ");
}
System.out.println("");
scanner.close();
}
}
