Уличная гонка
http://acm.pku.edu.cn/JudgeOnline/problem?id=1172
   
   На рисунке ниже изображен пример плана улиц для гонки. Вы видите точки, помеченные числами от 0 до N (где N = 9), а также стрелки, соединяющие их. Точка 0 является стартовой, а точка N - финишной. Стрелками представлены улицы с односторонним движением. Участники гонки передвигаются от точки к точке по улицам только в направлении стрелок. В каждой точке участник гонки может выбрать любую из исходящих стрелок.

http://acm.pku.edu.cn/JudgeOnline/images/1172_1.jpg

   Назовем план улиц "хорошим", если он обладает следующими свойствами:

   1. Каждая точка плана может быть достигнута со старта.
   2. Финиш может быть достигнут из любой точки плана.
   3. У финиша нет исходящих стрелок.

   Для достижения финиша участник не обязан пройти через все точки. Однако некоторые точки невозможно обойти. Назовем их "неизбежными". В примере такими точками являются точки 0, 3, 6 и 9. Для заданного "хорошего" плана ваша программа должна определить множество "неизбежных" точек (за исключением старта и финиша), которые должны посетить все участники (подзадача А).

   Предположим, что гонка проводиться за 2 последовательных дня. Для этой цели план должен быть разбит на два "хороших" плана, по одному на каждый день. В первый день точкой старта является точка 0, а финишем служит некая точка разбиения. Во второй день старт находится в этой точке разбиения, а финиш - в точке N. Для заданного "хорошего" плана ваша программа должна определить множество всех возможных точек разбиения (подзадача В). Точка S является точкой разбиения для "хорошего" плана C, если S отличается от старта и финиша С, и план разбивается на два "хороших" плана без общих стрелок и с единственной общей точкой S. В примере такой точкой разбиения является точка 3.

   Входные данные

   "Хороший" план содержит не более 50 точек и не более 100 стрелок. На вход подается N+1 строка. Первые N строк содержат конечные точки точки стрелок, исходящих, соответственно, из точек от 0 до N-1. Каждая из этих строк заканчивается числом -2. В последней строке содержится число -1.

   Выходные данные

   Выведите две строки. Первая строка должна содержать количество "неизбежных" точек в заданном плане, после чего в той же строке должны следовать номера этих точек в любом порядке (подзадача А). Вторая строка должна содержать количество точек разбиения в заданном плане, за которым в той же строке должны следовать номера этих точек в любом порядке (подзадача В).

   Пример входных данных

1 2 -2
3 -2
3 -2
5 4 -2
6 4 -2
6 -2
7 8 -2
9 -2
5 9 -2
-1

   Пример выходных данных

2 3 6
1 3

   Анализ условия и обсуждение идеи решения

   Пример решения на Pascal:

Код:
CONST Max_points = 50;
      Max_Arrows = 100;

TYPE Point_array = ARRAY [0..Max_points-1] OF BOOLEAN;

VAR input_file,output_file : text;
    current_arrow,current_point,number_of_points,number_of_arrows,
    number_unavoidable_points,number_splitting_points : INTEGER;
    Arrows : ARRAY [0..Max_Arrows-1,0..1] OF INTEGER;
    unavoidable,splitting : Point_array;

PROCEDURE initialisation;
BEGIN
  number_of_points:=1;
  number_of_arrows:=0;
  number_unavoidable_points:=0;
  number_splitting_points:=0;
  FOR current_point:=0 TO Max_points-1 DO
    BEGIN
      splitting [current_point]:=FALSE ;
      unavoidable [current_point]:=FALSE
    END;
END;

PROCEDURE read_input;
VAR num : INTEGER;
BEGIN
  read(num);
  WHILE NOT (num = -1) DO
  BEGIN
    IF num = -2
    THEN INC (number_of_points)
    ELSE BEGIN
           Arrows [number_of_arrows][0] := number_of_points-1;
           Arrows [number_of_arrows][1] := num;
           INC (number_of_arrows)
         END;
    read(num)
  END;
END;

PROCEDURE write_output;
BEGIN
  Write(number_unavoidable_points);
  FOR current_point:=1 TO number_of_points-2 DO
    IF unavoidable[current_point]
    THEN write(' ',current_point);
  Writeln;
  Write (number_splitting_points);
  FOR current_point:=1 TO number_of_points-2 DO
    IF splitting[current_point]
    THEN write(' ',current_point);
END;

PROCEDURE finalisation;
BEGIN
END;

PROCEDURE compute_results;

VAR reachable : Point_array;

  PROCEDURE find_reachable (current_point:INTEGER);
  VAR point:INTEGER;
      ready:BOOLEAN;
  BEGIN
    FOR point:=1 TO number_of_points - 1 DO
      reachable[point]:=FALSE;
    reachable[0]:=TRUE;
    ready:=FALSE;
    WHILE NOT ready DO
    BEGIN ready:=TRUE;
          FOR current_arrow:=0 TO number_of_arrows-1 DO
            IF reachable [Arrows[current_arrow,0]] AND
               NOT reachable [Arrows[current_arrow,1]] AND
               (Arrows[current_arrow,1]<>current_point)
            THEN BEGIN reachable[Arrows[current_arrow,1]]:=TRUE;
                       ready:=FALSE
                 END;
    END
  END;

  FUNCTION is_splitting:BOOLEAN;
  VAR current_arrow:INTEGER;
      OK:BOOLEAN;
  BEGIN
    current_arrow:=0;
    OK:=TRUE;
    WHILE (current_arrow<number_of_arrows) AND OK DO
    BEGIN
      OK:=reachable [Arrows[current_arrow,0]] OR
          NOT (reachable [Arrows [current_arrow,1]]);
      INC(current_arrow)
    END;
    is_splitting:=OK
  END;

BEGIN
  FOR current_point:=1 TO number_of_points-2 DO
    BEGIN
      find_reachable (current_point);
      IF NOT reachable[number_of_points-1]
      THEN BEGIN
             unavoidable [current_point] := TRUE;
             INC (number_unavoidable_points);
             IF is_splitting
             THEN BEGIN
                    splitting[current_point]:=TRUE;
                    INC (number_splitting_points)
                  END
           END
    END;
END;

BEGIN
  initialisation;
  read_input;
  compute_results;
  write_output;
  finalisation;
END.