-
Notifications
You must be signed in to change notification settings - Fork 0
/
d4_1238.java
58 lines (51 loc) · 1.39 KB
/
d4_1238.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package d4;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class d4_1238 {
public static int bfs(boolean[][]network, int s) {
Queue<Integer> q = new LinkedList<>(), cnt=new LinkedList<>();
boolean [] chk = new boolean[101];
q.add(s);
cnt.add(0);
chk[s]=true;
int max=s,prevcnt=0;
while(q.size()>0) {
int cur=q.poll(), curcnt=cnt.poll();
if(curcnt>prevcnt) {
prevcnt=curcnt;
max=cur;
}
else if(curcnt==prevcnt && max<cur)
max=cur;
for(int i=1;i<=100;i++) {
if(network[cur][i] && !chk[i]) {
chk[i]=true;
q.add(i);
cnt.add(curcnt+1);
}
}
}
return max;
}
public static void main(String args[]) throws Exception
{
int T=10;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for(int test_case = 1; test_case <= T; test_case++)
{
st = new StringTokenizer(br.readLine());
int n=Integer.parseInt(st.nextToken()), s = Integer.parseInt(st.nextToken());
boolean[][]network = new boolean[101][101];
st = new StringTokenizer(br.readLine());
for(int i=0;i<n/2;i++) {
int start = Integer.parseInt(st.nextToken()), end = Integer.parseInt(st.nextToken());
network[start][end]=true;
}
System.out.printf("#%d %d\n",test_case,bfs(network,s));
}
}
}