fork(1) download
copy 
  1. import java.awt.Dimension;
  2. import java.io.*;
  3. import static java.lang.Character.*;
  4. import static java.lang.Math.*;
  5. import java.math.BigDecimal.*;
  6. import java.math.BigInteger.*;
  7. import static java.math.BigInteger.*;
  8. import java.util.*;
  9. import static java.util.Arrays.*;
  10.  
  11.  
  12. //<editor-fold defaultstate="collapsed" desc="Main">
  13. class Ideone {
  14.     // https://n...content-available-to-author-only...s.org/kb/73/java/editor-codereference_ru.html#display
  15.  
  16.     private void run() {
  17.         try {
  18.             Locale.setDefault(Locale.US);
  19.         } catch (Exception e) {
  20.         }
  21.         boolean oj = true;
  22.         try {
  23.             oj = System.getProperty("MYLOCAL") == null;
  24.         } catch (Exception e) {
  25.         }
  26.  
  27.         if (oj) {
  28.             sc = new FastScanner(new InputStreamReader(System.in));
  29.             out = new PrintWriter(new OutputStreamWriter(System.out));
  30.         } else {
  31.             try {
  32.                 sc = new FastScanner(new FileReader("input.txt"));
  33.                 out = new PrintWriter(new FileWriter("output.txt"));
  34.             } catch (IOException e) {
  35.                 MLE();
  36.             }
  37.         }
  38.         Solver s = new Solver();
  39.         s.sc = sc;
  40.         s.out = out;
  41.         s.solve();
  42.         if (!oj) {
  43.             err.println("Time: " + (System.currentTimeMillis() - timeBegin) / 1e3);
  44.             err.printf("Mem: %d\n", (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) >> 20);
  45.         }
  46.         out.flush();
  47.     }
  48.  
  49.     private void show(int[] arr) {
  50.         for (int v : arr) {
  51.             err.print(" " + v);
  52.         }
  53.         err.println();
  54.     }
  55.  
  56.     public static void exit() {
  57.         err.println("Time: " + (System.currentTimeMillis() - timeBegin) / 1e3);
  58.         err.printf("Mem: %d\n", (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) >> 20);
  59.         out.flush();
  60.         out.close();
  61.         System.exit(0);
  62.     }
  63.  
  64.     public static void MLE() {
  65.         int[][] arr = new int[1024 * 1024][];
  66.         for (int i = 0; i < arr.length; i++) {
  67.             arr[i] = new int[1024 * 1024];
  68.         }
  69.     }
  70.  
  71.     public static void main(String[] args) {
  72.         new Ideone().run();
  73.     }
  74.  
  75.     static long timeBegin = System.currentTimeMillis();
  76.     static FastScanner sc;
  77.     static PrintWriter out;
  78.     static PrintStream err = System.err;
  79. }
  80.     //</editor-fold>
  81.  
  82. //<editor-fold defaultstate="collapsed" desc="FastScanner">
  83. class FastScanner {
  84.  
  85.     BufferedReader br;
  86.     StringTokenizer st;
  87.  
  88.     FastScanner(InputStreamReader reader) {
  89.         br = new BufferedReader(reader);
  90.         st = new StringTokenizer("");
  91.     }
  92.  
  93.     String next() {
  94.         while (!st.hasMoreElements()) {
  95.             try {
  96.                 st = new StringTokenizer(br.readLine());
  97.             } catch (Exception ex) {
  98.                 return null;
  99.             }
  100.         }
  101.         return st.nextToken();
  102.     }
  103.  
  104.     int nextInt() {
  105.         return Integer.parseInt(next());
  106.     }
  107.  
  108.     long nextLong() {
  109.         return Long.parseLong(next());
  110.     }
  111.  
  112.     double nextDouble() {
  113.         return Double.parseDouble(next());
  114.     }
  115.  
  116.     String nextLine() {
  117.         try {
  118.             return br.readLine();
  119.         } catch (IOException ex) {
  120.             return null;
  121.         }
  122.     }
  123. }
  124. //</editor-fold>
  125.  
  126. class Solver {
  127.  
  128.     void myAssert(boolean OK) {
  129.         if (!OK) {
  130.             Ideone.MLE();
  131.         }
  132.     }
  133.  
  134.     FastScanner sc;
  135.     PrintWriter out;
  136.     static PrintStream err = System.err;
  137.  
  138.     class Rib{
  139.         int to, w;
  140.  
  141.         Rib(int to, int w) {
  142.             this.to = to;
  143.             this.w = w;
  144.         }
  145.     }
  146.  
  147.     int n;
  148.     String[] place;
  149.     int[][] person;
  150.     ArrayList<Rib>[] gr;    
  151.     int[] color;
  152.     TreeSet<Integer>[] comp;
  153.  
  154.     void dfs( int v ){
  155.         comp[color[v]].add(v);
  156.         for( Rib r : gr[v] ){
  157.             if( color[r.to] == -1 ){
  158.                 color[r.to] = color[v] ^ r.w;
  159.                 dfs( r.to );
  160.             }
  161.             myAssert( color[r.to] == (color[v] ^ r.w) );
  162.         }
  163.     }
  164.  
  165.     void solve() {
  166.         n = sc.nextInt();
  167.         person = new int[n+1][];
  168.         place = new String[n+1];
  169.         for( int v = 1; v <= n; ++v ){
  170.             place[v] = sc.next();
  171.             person[v] = new int[sc.nextInt()];
  172.             for (int j = 0; j < person[v].length; j++)
  173.                 person[v][j] = sc.nextInt();
  174.         }
  175.  
  176.         gr = new ArrayList[n+1];
  177.         for (int v = 1; v <= n; v++)
  178.             gr[v] = new ArrayList<>();
  179.  
  180.  
  181.         for( int v = 1; v <= n; ++v ){
  182.             for( int to : person[v] ){
  183.                 if( place[v].equals(place[to]) ){
  184.                     gr[v ].add(new Rib(to, 0));
  185.                     gr[to].add(new Rib( v, 0));
  186.                 }
  187.                 else{
  188.                     gr[v ].add(new Rib(to, 1));
  189.                     gr[to].add(new Rib( v, 1));
  190.                 }
  191.             }
  192.         }
  193.  
  194.         TreeSet<Integer> ans  = getAns();
  195.  
  196.         out.println( ans.size() );
  197.         for (Integer v : ans) {
  198.             out.print( " " + v );
  199.             myAssert( 1 <= v && v <= n );
  200.         }
  201.         out.println();
  202.     } 
  203.  
  204.     TreeSet<Integer> getAns() {
  205.         TreeSet<Integer> ans = new TreeSet<>();
  206.         color = new int[n+1];
  207.         fill( color, -1 );
  208.         //int cntUsedVertex = 0;
  209.         for (int v = 1; v <= n; v++) {
  210.             if( color[v] == -1 ){
  211.                 color[v] = 0;
  212.                 comp = new TreeSet[2];
  213.                 comp[0] = new TreeSet<>();
  214.                 comp[1] = new TreeSet<>();
  215.                 dfs( v );
  216.                 //cntUsedVertex += comp[0].size() + comp[1].size();
  217.                 if( comp[0].size() <= comp[1].size() )
  218.                     ans.addAll(comp[0]);
  219.                 else
  220.                     ans.addAll(comp[1]);
  221.             }
  222.         }
  223.         //myAssert( cntUsedVertex == n );
  224.         if( ans.isEmpty() ) ans.add(1);
  225.         return ans;
  226.     }
  227.  
  228. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
3
A  1   3
WC 1   3
WC 0
stdout
copy 
1
 1
https://ideone.com/a9EPDj
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!