import java.io.PrintStream; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner; /** * Solution to Rainbow Roads * * @author vanb */ public class rainbow_bfs_faster_vanb { private static Scanner sc; private static PrintStream ps; /** * Capture info for a Road. It's like an edge of a graph. * The roads are 2-way roads, but we'll implement each as 2 one-way roads. * * @author vanb * */ private class Road { /** Start, end */ public Intersection source, destination; /** Color */ public int color; /** * Create a Road. * * @param source Start * @param destination End * @param color Color */ public Road( Intersection source, Intersection destination, int color ) { this.source = source; this.destination = destination; this.color = color; } /** * A pretty String for debugging. * * @return A pretty String for debugging */ public String toString() { return "[src:" + source.index + " dst:" + destination.index + "]"; } } /** * An Intersection. It's like a node of a graph. * * @author vanb */ private class Intersection { /** Has this intersection been eliminated from being 'Super'? */ public boolean eliminated = false; /** A list of outbound roads */ public List roads = new LinkedList(); /** The number of this Intersection */ public int index; /** * Create an Intersection. All we need for now is the index. * * @param index This Intersection's number */ public Intersection( int index ) { this.index = index; } } /** * Do it! */ private void doit() { int n = sc.nextInt(); Intersection intersections[] = new Intersection[n]; // Create the Intersections for( int i=0; i q = new ArrayDeque(n+n); for( Intersection intersection : intersections ) { // OK, here's the trick. Consider this graph: // // B // | // 1 // | // A--1--X--2--C // // There's a road between A and X color 1, B and X color 1, C and X color 2. // You cannot get from A to B without repeating color 1 on consecutive roads, // so they're not Super. X and C are Super, since you can get from them to // every other node on a Rainbow Road. // // But, think about this: It's not just A and B that are eliminated, but also // any nodes in their subtrees! That gives us our strategy: // // Find nodes with outbound roads of the same color, and eliminate all of the // nodes in those subtrees from being Super. // // So, first, for each intersection, see if there are any repeated colors // in the outbound roads. for( Road road : intersection.roads ) { // Is this the first time we've seen this color at this intersection? if( last[road.color]!=intersection.index ) { last[road.color] = intersection.index; colors[road.color] = 1; } else colors[road.color]++; } // Put all of those duplicate color roads on a queue. // We'll use a BFS later to eliminate their destinations and all of their subtrees. Iterator it = intersection.roads.iterator(); while( it.hasNext() ) { Road road = it.next(); if( colors[road.color]>1 ) { q.add( road ); // Here's a bit of a trick to speed things up. // Since this is a BFS, we'll visit each road at most once. // Once we visit it, we'll never need to consider it again. // So, rather than marking it as 'visited', we'll remove it entirely. it.remove(); } } } // OK, now use a BFS to eliminate all of the nodes // in those bad subtrees. while( !q.isEmpty() ) { Road road = q.poll(); // Eliminate the Intersection if we haven't done so already. // Note that while we'll visit each road at most once, // it is possible to visit an Intersection more than once. if( !road.destination.eliminated ) { road.destination.eliminated = true; // That's one less Super candidate --count; } // Now, keep going down the tree Iterator it = road.destination.roads.iterator(); while( it.hasNext() ) { Road nextroad = it.next(); // Don't go back up! if( nextroad.destination!=road.source ) { q.add( nextroad ); // Here's that trick again. it.remove(); } } } // Nothing left to do but print the answer. ps.println( count ); for( Intersection intersection : intersections ) if( !intersection.eliminated ) { ps.println( intersection.index ); } } /** * Main! * * @param args Command-line args (not used) * @throws Exception */ public static void main( String[] args ) throws Exception { sc = new Scanner( System.in ); ps = System.out; new rainbow_bfs_faster_vanb().doit(); } }