package com.daxiong.arithmetic;
import java.io.*;
import java.util.*;
public class BFS {
static int[][] data;
static int vertex,depen,start,end;
static int[] queue;
static int[] visit;
public static void main(String[] args) throws Exception{
Scanner sc =
new Scanner(
new File(
"src/case/bfs.txt"));
vertex = sc.nextInt();
data =
new int[(vertex+
1)][(vertex +
1)];
depen = sc.nextInt();
for(
int i =
0;i < depen;i++){
data[sc.nextInt()][sc.nextInt()] =
1;
}
sc.close();
queue =
new int[
100];
visit =
new int[
100];
start =
1;
end =
0;
queue[end++] =
8;
visit[
0] =
1;
print();
bfs(
8,
2,
1);
for(
int i =
0;i <
20;i++){
System.
out.println(queue[i] +
" : " + visit[i]);
}
}
static void bfs(
int row,
int step,
int curStep){
int temp =
0;
int start_temp =
0;
if(row > vertex){
return;
}
if(start > end){
return;
}
for(
int i =
1;i <= vertex;i++){
if(data[row][i] !=
0){
temp = end;
queue[temp] = i;
visit[temp] = step;
end++;
}
}
start_temp = start;
int col = queue[start_temp];
start++;
if(visit[start_temp] <= curStep){
bfs(col,step,visit[start_temp]);
}
else {
bfs(col,step+
1,visit[start_temp]);
}
}
static void print(){
for(
int i =
1;i <= vertex;i++){
for(
int j =
1;j <= vertex;j++){
System.
out.print(data[i][j] +
" ");
}
System.
out.println();
}
System.
out.println();
}
}
