В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Будем считать, что процессы выполняются одновременно, в случае если есть хотя бы один момент времени, когда оба процесса выполнялись. Найдите количество процессов, которые могли выполняться одновременно с процессом номер 13 (не обязательно все одновременно).
| ID процесса B |
Время выполнения процесса B (мс) |
ID процесса(ов) A |
| 1 |
4 |
0 |
| 2 |
3 |
1 |
| 3 |
1 |
2 |
| 4 |
7 |
0 |
| 5 |
6 |
1; 4 |
Пояснение к примеру: допустим нам нужно определить количество процессов, которые могли выполняться одновременно с процессом 2. Процессы 1 и 3 не подходят, т.к. процесс 2 можно запустить только после выполнения процесса 1, а процесс 3 только после выполнения процесса 2. Процесс 4 подходит в случае, если процесс 1 был запущен в самом начале, сразу после него был запущен процесс 2 (через 4 мс после начала работы программы) и процесс 4 также был запущен сразу после начала работы программы (тогда с 4 по 7 мс процессы 2 и 4 выполнялись совместно).
Процесс 5 подходит, в случае, если запустить процесс 4 в самом начале, и сразу после него (через 7 мс после начала работы программы) запустить процесс 5. Процесс 1 же можно запустить через 3 мс после начала работы программы (тогда закончится он к 7 мс). И сразу после него запустить процесс 2. Тогда с 7 мс по 10 мс процесс 2 и 5 будут выполняться совместно.
Файл к заданию