Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.HashMap;
- import java.util.HashSet;
- import java.util.Set;
- import java.util.StringTokenizer;
- import acm.program.ConsoleProgram;
- public class TopologicalSorting extends ConsoleProgram {
- public void run() {
- HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
- String s = readLine("Enter n of subjects and n of limitations: ");
- int subject = 0, limit = 0;
- StringTokenizer tk = new StringTokenizer(s);
- subject = Integer.valueOf(tk.nextToken());
- limit = Integer.valueOf(tk.nextToken());
- for (int i = 0; i < limit; i++) {
- int pre = 0, sub = 0;
- String lim = readLine();
- StringTokenizer tok = new StringTokenizer(lim);
- pre = Integer.valueOf(tok.nextToken());
- sub = Integer.valueOf(tok.nextToken());
- if (map.containsKey(sub)) {
- ArrayList<Integer> array = map.get(sub);
- array.add(pre);
- map.put(sub, array);
- } else {
- ArrayList<Integer> array = new ArrayList<Integer>();
- array.add(pre);
- map.put(sub, array);
- }
- }
- Set<Integer> set = new HashSet<Integer>();
- String sequence = readLine("Enter sequence: ");
- StringTokenizer tok = new StringTokenizer(sequence);
- set.add(Integer.valueOf(tok.nextToken()));
- while (tok.hasMoreTokens()) {
- int i = Integer.valueOf(tok.nextToken());
- if (!map.containsKey(i)) continue;
- for (int j = 0; j < map.get(i).size(); j++) {
- if (!set.contains(map.get(i).get(j))) {
- println("false");
- return;
- }
- }
- set.add(i);
- }
- println("true");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement