DFS_AdjMatrix.java

importjava.lang.*;
importjava.util.*;
importjava.math.*;
importjava.io.*;
/*
 * Author : joney_000[let_me_start]
 * Algorithm : DFS using AdjMatrix O(V^2)
 * Platform : CodeForces
 */
classDfsAdjencyMatrix {

privatestaticBufferedReaderbr = newBufferedReader(newInputStreamReader(System.in),2000);;
privatestaticBufferedWriterout = newBufferedWriter(newOutputStreamWriter(System.out),2000);
/* private static BufferedReader = new BufferedReader(new FileReader("input.txt"));
 private static BufferedWriter out= new BufferedWriter(new FileWriter("output.txt"));
 */
publicDfsAdjencyMatrix(){

 }

publicstaticvoidmain(String[] args)throwsException{

inttests = Integer.parseInt(br.readLine());
for(intt=1;t<=tests;t++){
// End Of File str = br.readLine(); if (str ==null || str.length()==0) break;
String []s = br.readLine().split(" ");

intn = Integer.parseInt(s[0]); //int m = Integer.parseInt(s[1]);
intadj[][] = newint[n+1][n+1];
for(inti=1;i<=n;i++){
s = br.readLine().split(" ");
for(intj=1;j<=n;j++){
adj[i][j] = Integer.parseInt(s[j-1]);
 }
 }
booleanvis[] = newboolean[n+1]; // indexing [1..n]
intsrc = 1;
dfs(adj,vis,src,n);
out.flush();
 }

 }
// DFS-BFS
publicstaticvoiddfs(int[][]adj ,boolean[] vis ,intsrc ,intn)throwsException{

LinkedList<Integer> stack = newLinkedList<Integer>();
stack.addLast(src);
vis[src] = true;
intlevel = 0;
// print(src,level);
while(!stack.isEmpty()){
intnode = stack.getLast(); // DFS-BFS Decesion
intcheck = 0;
for(intj=1;j<=n;j++){
if(adj[node][j]==1 && (!vis[j])){
check = 1;
level++;
stack.addLast(j);
// print(j,level); 
vis[j]=true;
break;
 }

 }

// DFS-BFS Decesion remove IF Block
if(check==0){
//adj[node][1..n] is empty
stack.removeLast();
level--;
 }
 }
 }
publicstaticvoidprint(intnode , intlevel)throwsException{

out.write(" node="+node+" its depth="+level+"\n");
 }
}