Подскажите как решается эта задача:http://informatics.mccme.ru/moodle/mod/ … rid=1255#1
Спасибо
1 2011-09-19 18:21:05
Тема: Перекрывающиеся прямоугольники (0 ответов, оставленных в Problems)
2 2011-09-18 19:44:26
Re: Поиск цикла (9 ответов, оставленных в Problems)
Написал аналогично на дельфи и сдал.
Медленно работало на c++ видимо из-за векторов для хранения ребер.
3 2011-09-15 00:14:28
Re: Поиск цикла (9 ответов, оставленных в Problems)
Я имею ввиду, что тот код, что в первом сообщении получает TLE, а если выводить вершины цикла не в конце, а сразу при нахождении и завершать программу(как в сообщении 5), то он не компилится на сервере.
Я решаю на http://neerc.ifmo.ru/president/11/index.html
Могу в личку написать вам пароль.
4 2011-09-14 23:50:33
Re: Поиск цикла (9 ответов, оставленных в Problems)
Сообщение о конкретной ошибке не пишут.
Условие лаконичное: дан ориентированный невзвешенный граф, требуется найти любой цикл и вывести его в порядке обхода цикла. (1<=n<=10^5;1<=m<=10^5).
Условие почти дословно.
Код стал падать когда добавилась процедура print(), выводящая цикл и завершающая программу(видимо криво завершается).
5 2011-09-14 21:35:29
Re: Поиск цикла (9 ответов, оставленных в Problems)
Конечно цикл - компонента сильной связности, я их как-то даже не ассоциировал, и вообще, они ищутся дольше - 2-мя поисками в глубину и сортировкой вместо одного.
И, кстати, завершать программу в c++ из глубокой рекурсии командой exit(0) нормально?
А ссылку я могу дать, только туда вход по паролю, могу написать вам, если вы готовы!
Вот это вот получает compilation error(как только встречаем цикл, выводим его и выходим из программы - у меня работает)
#include <stdio.h>
#include <vector>
using namespace std;
vector <int> g[100001];
int color[100001],p[100001];
int f=-1,s=-1;
void print() {
int res[100001];
int e=1;
res[1]=f;
int v=p[f];
while (v!=s)
{ e++; res[e]=v;;
v=p[v]; }
e++; res[e]=s;
printf("YES\n");
for (int i=e;i>=1;i--) printf("%d ",res[i]);
exit(0);
}
void dfs(int u) {
color[u]=1;
for (int i=0;i<g[u].size();i++)
if (color[g[u][i]]==0) {p[g[u][i]]=u; dfs(g[u][i]); } else
if (color[g[u][i]]==1) {f=u; s=g[u][i]; p[s]=u; print(); }
color[u]=2;
}
int main() {
int n,m;
freopen("cycle.in","r",stdin);
freopen("cycle.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
}
for (int i=1;i<=n;i++)
if (color[i]==0) dfs(i);
printf("NO");
return 0;
}
6 2011-09-14 15:29:11
Re: Поиск цикла (9 ответов, оставленных в Problems)
А каким образом мне поможет нахождение компонент сильной связности?
7 2011-09-14 00:35:10
Тема: Поиск цикла (9 ответов, оставленных в Problems)
Требуется в ориентированном графе найти цикл и вывести его (1<=n<=100000;1<=m<=100000)
Данный код получает TLE, даже когда его переделал под пример из статьи http://e-maxx.ru/algo/finding_cycle
#include <stdio.h>
#include <vector>
using namespace std;
vector <int> g[100001];
int color[100001],p[100001];
int f=-1,s=-1;
bool dfs(int u) {
color[u]=1;
for (int i=0;i<g[u].size();i++)
if (color[g[u][i]]==0) {p[g[u][i]]=u; if ( dfs(g[u][i]) ) return true;} else
if (color[g[u][i]]==1) {f=u; s=g[u][i]; p[s]=u; return true; }
color[u]=2;
return false;
}
int main() {
int n,m;
freopen("cycle.in","r",stdin);
freopen("cycle.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
}
for (int i=1;i<=n;i++)
if (color[i]==0)
if (dfs(i)) break;
if (s==-1) printf("NO"); else
{ vector <int> res;
res.push_back(f);
int v=p[f];
while (v!=s)
{ res.push_back(v);
v=p[v]; }
res.push_back(s);
printf("YES\n");
for (int i=res.size()-1;i>=0;i--) printf("%d ",res[i]);
}
return 0;
}
Прошу указать на мою ошибку!
Спасибо.