5107. Маршрутка

 

Маршрутка города Менделеево движется согласно маршруту от остановки номер 1 до остановки номер m. Водитель останавливается на остановке только, если хотя бы один из пассажиров, находящихся в салоне, хочет на ней выйти. При этом все пассажиры, ожидающие маршрутку на этой остановке, садятся в неё (количество пассажирских мест не ограничено). Поскольку маршрутка начинает движение от остановки номер 1, то все пассажиры, находящиеся на ней, сразу садятся в маршрутку.

Требуется по списку пассажиров определить номера остановок, на которых остановится маршрутка. Гарантируется, что хотя бы один пассажир ожидает маршрутку на остановке номер 1.

 

Вход. В первой строке записано два натуральных числа n, m (1 ≤ n ≤ 105, 1 ≤ m ≤ 109) – количество пассажиров и остановок соответственно.

Далее записано n строк по два натуральных числа li – номер остановки на которой ожидает маршрутку i-ый пассажир, ri – номер остановки, на которой выходит i-ый пассажир (1 ≤ li < ri ≤ m).

 

Выход. Выведите в первой строке количество остановок k, на которых маршрутка остановится. Далее выведите k строк – номера этих остановок в возрастающем порядке.

 

Пример входа

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

6 11

1 4

2 3

4 5

2 5

4 7

4 10

5

1

4

5

7

10

 

 

РЕШЕНИЕ

графы

 

Анализ алгоритма

Построим ориентированный граф, вершинами которого будут остановки, а ребра пассажирами, соединяющими вершины li и ri. Поскольку число вершин графа (остановок) m ≤ 109, а граф разреженный (количество ребер n ≤ 105), то список смежности g зададим структурой map<int,vector<int> > g – каждой вершине поставим в соответствие список смежности, хранящийся в векторе. Для запоминания пройденных вершин в качестве структуры used будем использовать множество set<int>.

 

Запустим поиск в глубину из вершины 1. Вершины, которые посетит поиск (которые будут занесены в used), и есть номера остановок, в которых остановится маршрутка.

Реализация алгоритма

Объявим список смежности графа g, а также множество посещенных вершин used.

 

set<int> used;

set<int>::iterator iter;

map<int,vector<int> > g;

 

Поиск в глубину из вершины v.

 

void dfs(int v)

{

 

Отмечаем вершину v пройденной.

 

  used.insert(v);

 

Перебираем вершины, смежные с v.

 

  for(int i = 0; i < g[v].size(); i++)

  {

 

В графе имеется ребро (v, to).

 

    int to = g[v][i];

 

Если вершина to еще не пройдена, то запускаем поиск в глубину из to.

 

    if(used.find(to) == used.end()) dfs(to);

  }

}

 

Основная часть программы. Читаем входные данные, строим граф.

 

scanf("%d %d",&n,&m);

for(i = 0; i < n; ++i)

{

  scanf("%d %d",&x,&y);

  g[x].push_back(y);

}

 

Запускаем поиск в глубину из вершины 1.

 

dfs(1);

 

Выводим список посещенных вершин – номера остановок, где будет останавливаться маршрутка.

 

printf("%d\n",used.size());

for(iter = used.begin(); iter != used.end(); iter++)

  printf("%d\n",*iter);