Guest User

sequence land

a guest
Mar 10th, 2018
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.10 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.*;
  5.  
  6. import static java.lang.Integer.parseInt;
  7.  
  8. /**
  9.  * Created by bugkiller on 10/03/18.
  10.  */
  11.  
  12. class SequenceLand {
  13.  
  14.     static Set<Integer> a[] = new Set[301];
  15.     static boolean vis[] = new boolean[301];
  16.  
  17.     public static void main(String[] args) throws IOException {
  18.  
  19.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  20.         String s[];
  21.         int n, k;
  22.         s = br.readLine().split("\\s");
  23.         n = parseInt(s[0]);
  24.         k = parseInt(s[1]);
  25.         for (int i = 0; i < n; i++) {
  26.             s = br.readLine().split("\\s");
  27.             a[i] = new HashSet<>();
  28.             for (int j = 1; j <= parseInt(s[0]); j++) {
  29.                 a[i].add(parseInt(s[j]));
  30.             }
  31.         }
  32.         System.out.println(solve(n,k));
  33.  
  34.     }
  35.  
  36.     private static int solve(int n, int k) {
  37.         Arrays.fill(vis, false);
  38.         return bfs(n,k);
  39.     }
  40.  
  41.     private static int bfs(int n, int k) {
  42.         int ans = 1;
  43.         Queue<Integer> queue = new LinkedList<>();
  44.         queue.add(0);
  45.         while (!queue.isEmpty()) {
  46.             int x = queue.poll();
  47.             vis[x] = true;
  48.             List adj = adjElementsOf(x, n, k);
  49.             ans += adj.size();
  50.             queue.addAll(adj);
  51.         }
  52.         return ans;
  53.     }
  54.  
  55.     private static List<Integer> adjElementsOf(int x, int n, int k) {
  56.  
  57.         List<Integer> adjElements = new ArrayList<>();
  58.         for (int i = 0; i < n; i++) {
  59.             if (!vis[i]) {
  60.                 if (isAdj(i, x, k)) {
  61.                     adjElements.add(i);
  62.                 }
  63.             }
  64.         }
  65.         return adjElements;
  66.     }
  67.  
  68.     //is i could be included in adj list of x
  69.     private static boolean isAdj(int i, int x, int k) {
  70.         int cnt = 0;
  71.         for (int d : a[x]) {
  72.             if (a[i].contains(d)) {
  73.                 cnt++;
  74.             }
  75.         }
  76.         if (cnt >= k) {
  77.             vis[i] = true;
  78.             return true;
  79.         }
  80.         return false;
  81.     }
  82.  
  83. }
Add Comment
Please, Sign In to add comment