Мальчик Вася очень любит
разворачивать ориентированные графы. Помогите ему в этом.
Вход. Первым записано число n
(1 ≤ n ≤ 50000) –
количество вершин в графе. В следующих n
строках записан граф в виде списков смежности: в i-ой строке, в порядке возрастания, записаны номера вершин, в
которые идут рёбра из i-ой вершины.
Нумерация начинается с единицы. Гарантируется, что рёбер в графе не более
50000.
Выход. Выведите
развёрнутый граф в том же формате, что и исходный.
|
Пример
входа 1 |
Пример
выхода 1 |
|
4 2 3 3 2 |
4 1 4 1 2 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
2 2 1 |
2 2 1 |
графы –
список смежности
Анализ алгоритма
Считываем
входной граф, обращаем каждое его ребро и строим список смежности развёрнутого
графа. Выводим полученный граф.
Реализация алгоритма
Граф храним в
списке смежности g. Объявим рабочий символьный массив s.
#define MAX 500010
vector<vector<int> > g;
char s[MAX];
Читаем количество вершин графа n.
scanf("%d",&n); gets(s);
g.resize(n + 1);
Читаем построчно входной граф.
for(i = 1; i <= n; i++)
{
gets(s);
stringstream ss(s);
Разбиваем строку s
на набор лексем. Если в i-ой строке
встретилось число val, то входной
граф содержит ребро i ® val. Обернутый граф должен содержать ребро val ® i, заносим в
массив g[val] число i.
while (ss
>> val)
g[val].push_back(i);
}
Выводим количество вершин результирующего графа.
printf("%d\n",n);
Выводим список смежности.
for(i = 1; i <= n; i++)
{
if
(g[i].size())
{
printf("%d",g[i][0]);
for(j = 1; j < g[i].size(); j++)
printf("
%d",g[i][j]);
}
puts("");
}