Guest User

Untitled

a guest
Jul 22nd, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.14 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.HashSet;
  3. import java.util.LinkedList;
  4. import java.util.List;
  5. import java.util.Queue;
  6. import java.util.Scanner;
  7. import java.util.Set;
  8.  
  9. /**
  10. * All index start from 0, ... - 1 when getting input
  11. * use crates
  12. *
  13. *
  14. * @author reobj_
  15. *
  16. */
  17. public class Main {
  18.  
  19. public static void main(String[] args) {
  20. Scanner consoleIn = new Scanner(System.in);
  21.  
  22. int amountCows = consoleIn.nextInt();
  23. int amountGroups = consoleIn.nextInt();
  24. // int ans = 0;
  25.  
  26. Set<Integer> invites = new HashSet<Integer>();
  27. invites.add(1);
  28.  
  29. Set[] groups = new HashSet[amountGroups];
  30. for(int i = 0; i < amountGroups; i++) {
  31. groups[i] = new HashSet<Integer>();
  32. }
  33.  
  34. // Input
  35. for(int i = 0; i < amountGroups; i++) {
  36. int amount = consoleIn.nextInt(); // Per group
  37.  
  38. for(int j = 0; j < amount; j++) {
  39. int in = consoleIn.nextInt();
  40. groups[i].add(in);
  41. }
  42. }
  43.  
  44.  
  45. // Buffer for invitation, if this one is cleared means
  46. // you got the minimum amount that needs to be invited
  47. Queue<Integer> toCheck = new LinkedList<Integer>();
  48. toCheck.add(1); // Default invited cow
  49. while(!toCheck.isEmpty()) {
  50. int current = toCheck.remove(); // Process next element in side queue
  51. invites.add(current); // Invite, which's checked
  52. // ans++;
  53.  
  54. for(int j = 0; j < amountGroups; j++) {
  55. if(groups[j].size() == 0) continue;
  56.  
  57. groups[j].remove(current); // Take out i, like 1 (first time)
  58.  
  59. // Only one cow's left, must be invited
  60. if(groups[j].size() == 1) {
  61. // Pop out the (last) element in the set
  62. toCheck.add( (Integer) groups[j].iterator().next() );
  63. }
  64. }
  65. }
  66.  
  67. System.out.println( invites.size() );
  68. // System.out.println(ans);
  69.  
  70. consoleIn.close();
  71. }
  72.  
  73.  
  74. }
Add Comment
Please, Sign In to add comment