-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMain2.java
More file actions
120 lines (100 loc) · 3.74 KB
/
Copy pathMain2.java
File metadata and controls
120 lines (100 loc) · 3.74 KB
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
package com;
import java.io.*;
import java.util.*;
public class Main2 {
private static class Person {
public int id;
public boolean seen;
public ArrayList<Person> shorter;
public ArrayList<Person> taller;
public Person(int id) {
this.id = id;
this.seen = false;
shorter = new ArrayList<>();
taller = new ArrayList<>();
}
}
// DFS
public static boolean searchForShorter(Person source, Person target) {
Queue<Person> peopleToCheck = new LinkedList<>();
peopleToCheck.addAll(source.shorter);
while(!peopleToCheck.isEmpty()) {
Person nextPerson = peopleToCheck.remove();
if(!nextPerson.seen) {
nextPerson.seen = true;
if(nextPerson.id == target.id) {
return true;
}
for(Person friend : nextPerson.shorter) {
if(!friend.seen){
peopleToCheck.add(friend);
}
}
}
}
return false;
}
public static boolean searchForTaller(Person source, Person target) {
Queue<Person> peopleToCheck = new LinkedList<>();
peopleToCheck.addAll(source.taller);
while(!peopleToCheck.isEmpty()) {
Person nextPerson = peopleToCheck.remove();
if(!nextPerson.seen) {
nextPerson.seen = true;
if(nextPerson.id == target.id) {
return true;
}
for(Person friend : nextPerson.taller) {
if(!friend.seen){
peopleToCheck.add(friend);
}
}
}
}
return false;
}
public static void main(String[] args) {
try{
// Scanner in = new Scanner(System.in);
BufferedReader in = new BufferedReader (new InputStreamReader (System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int noOfPeople = Integer.parseInt(st.nextToken());
Map<Integer, Person> people = new HashMap<>();
for(int i = 1; i <= noOfPeople; i++) {
people.put(i, new Person(i));
}
int noOfComparisons = Integer.parseInt(st.nextToken());
for(int i = 0; i < noOfComparisons; i++) {
st = new StringTokenizer(in.readLine());
int first = Integer.parseInt(st.nextToken());
int second = Integer.parseInt(st.nextToken());
Person firstPerson = people.get(first);
Person secondPerson = people.get(second);
firstPerson.shorter.add(secondPerson);
secondPerson.taller.add(firstPerson);
}
st = new StringTokenizer(in.readLine());
int taller = Integer.parseInt(st.nextToken());
int shorter = Integer.parseInt(st.nextToken());
Person tallerPerson = people.get(taller);
Person shorterPerson = people.get(shorter);
if(tallerPerson == null || shorterPerson == null) {
System.out.println("unknown");
return;
}
if(searchForShorter(tallerPerson, shorterPerson)) {
System.out.println("yes");
for (Person person: people.values()) {
person.seen = false;
}
} else if(searchForTaller(tallerPerson, shorterPerson)) {
System.out.println("no");
} else {
System.out.println("unknown");
}
}
catch(IOException e){
System.out.println("IO: General");
}
}
}