Сегодня писал контест и там попалась вот такая задача:
Мэр города Гадюкино решил проверить состояние дорог после только что проведенного капитального ремонта. Для этого он хочет проехать по каждой дороге в обоих направлениях. Помогите мэру составить кратчайший маршрут, проходящий по каждой дороге в каждом направлении хотя бы один раз.
В городе Гадюкино n перекрестков и m дорог, каждая из которых соединяет два различных перекрестка. Между двумя перекрестками может быть не более одной дороги. Известно, что по дорогам от каждого перекрестка можно доехать до любого другого.
Входные данные
Входной файл содержит целые числа n и m (1 ≤ n ≤ 104, 1 ≤ m ≤ 105), и далее m пар целых чисел ai и bi - номера перекрестков, которые соединяет i-я дорога.
Выходные данные
В выходной файл выведите число s - минимальную длину пути и далее s+1 число - номера перекрестков в том порядке, в котором их нужно проезжать.
Я получил по ней 90 баллов нахождением Эйлерова пути в ориентированном графе, но мне кажется, что это не я напортачил, а просто плохой алгоритм решения. Вообщем у кого какие идеи решения? Поделитесь.
Например я не понял обязательно ли граф связен. Если нет, то вы могли потерять случай изолированных вершин и еще много чего. Например задавный, о не уверен, что допустимый тест.3 1 2 3.Не умею читать.#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<stdlib.h>
#include<math.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define FOR(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int n,m,c=0,x,y,d[200001],h[200001],s[200001],ne[200001];
void dfs(int v)
{
int j=h[v];
while (j!=0)
{
h[v]=0;
dfs(s[j]);
j=ne[j];
}
c++; d[c]=v;
}
void read()
{
cin>>n>>m;
For(i,1,m)
{
cin>>x>>y;
s[i]=y;
ne[i]=h[x];
h[x]=i;
s[i+m]=x;
ne[i+m]=h[y];
h[y]=i+m;
}
}
void solve()
{
dfs(1); // graf svyaznyi
}
void write()
{
cout<<c-1<<endl;
FOR(i,c,1) cout<<d[i]<<" ";
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
read();
solve();
write();
return 0;
}
Подскажите пожалуйста, где можно почитать про такой способ представления графа?
Это хреновый способ, лучше просто хранить в виде динамического двумерного массива: vector<vector> g(n);
Уау! Какого это, когда на твой коммент отвечают через 8 лет?
Прикольно)
Я недавно встретил задачку, в которой способ с vector g, давал жесткий МЛ, когда этот(как мне показалось), неплохо справлялся. https://drive.google.com/open?id=0B-igere9jCTBamVPSzhHQXN1ak12RzNoSDktSXR3TkJ4eU5v Задача "Олимпийские Авиалинии".
http://kvodo.ru/adjacency-list.html Но, я бы не рекомендовал тратить на это время, т.к. после изучения простого динамического двумерного массива, я больше не использовал списки смежности.
Минимальная длина пути, насколько я понимаю, всегда будет равна 2*m.