Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Graph {
LinkedList<Pair> adj[];
int vertex;
boolean[] isVisited;
public Graph(int vertex) {
this.vertex = vertex;
isVisited = new boolean[vertex + 1];
adj = new LinkedList[vertex + 1];
for(int i = 1; i <= vertex; i++) {
adj[i] = new LinkedList<Pair>();
}
}
class Pair {
int first;
int weight;
public Pair(int first, int weight) {
this.first = first;
this.weight = weight;
}
}
void addEdge(int source, int destination, int weight) {
adj[source].add(new Pair(destination, weight));
adj[destination].add(new Pair(source, weight));
}
public void dfs(int source){
isVisited[source] = true;
// System.out.println(source);
if(adj[source].size() == 0) return;
for(Pair x: adj[source]) {
if(!isVisited[x.first]) {
this.dfs(x.first);
}
}
}
public void bfs(int source) {
Queue<Integer> q = new LinkedList<Integer>();
isVisited[source] = true;
q.add(source);
while(q.size() != 0) {
int current = q.poll();
// System.out.println(current);
Iterator<Pair> n = adj[current].listIterator();
while(n.hasNext()) {
int i = (int) n.next().first;
if(!isVisited[i]) {
isVisited[i] = true;
q.add(i);
}
}
}
}
public int getConnectedGraphs(Graph g) {
int connectedGraphs = 0;
for(int i = 1; i <= 5; i++) {
if(!g.isVisited[i]) {
g.dfs(i);
connectedGraphs++;
}
}
return connectedGraphs;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int row = sc.nextInt();
int col = sc.nextInt();
System.out.format("Row: %d - Col: %d", row, col);
sc.nextLine();
int matrix[][] = new int[row][col];
for(int i = 0; i < row; i++) {
String line = sc.nextLine();
for(int j = 0; j < col; j++) {
matrix[i][j] = line.charAt(j);
}
}
int connectedGraphs = 0;
boolean[][] visited = new boolean[row][col];
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(!visited[i][j] && matrix[i][j] != '0') {
BFS(i,j, matrix, visited);
connectedGraphs++;
}
}
}
System.out.println("Cound: " + connectedGraphs);
}
static void BFS(int i, int j, int[][] matrix, boolean[][] visited){
if(matrix[i][j] == 'X' && !visited[i][j]){
visited[i][j] = true;
if(i < matrix.length-1) BFS(i+1,j, matrix, visited);
if(j < matrix[i].length-1) BFS(i, j+1, matrix, visited);
if(i > 0) BFS(i-1, j, matrix, visited);
if(j > 0) BFS(i, j-1, matrix, visited);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.