1 Тема от Coder Отредактировано Coder (2011-09-14 00:35:28)

  • Coder
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-09-11
  • Сообщений: 7

Тема: Поиск цикла

Требуется в ориентированном графе найти цикл и вывести его (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;
}

Прошу указать на мою ошибку!
Спасибо.

2 Ответ от aza_inf

  • aza_inf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-30
  • Сообщений: 78

Re: Поиск цикла

еще можно использовать это http://e-maxx.ru/algo/strong_connected_components.

3 Ответ от Coder

  • Coder
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-09-11
  • Сообщений: 7

Re: Поиск цикла

А каким образом мне поможет нахождение компонент сильной связности?

4 Ответ от aza_inf

  • aza_inf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-30
  • Сообщений: 78

Re: Поиск цикла

Можно ссылку на задачу?!
Компонентой сильной связности (strongly connected component) называется такое (максимальное по включению) подмножество вершин , что любые две вершины этого подмножества достижимы друг из друга.
То есть это и есть цикл.
И вообще можно оптимизировать вашу программу, заменив векторы на массивы, вроде.

5 Ответ от Coder Отредактировано Coder (2011-09-14 21:53:06)

  • Coder
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-09-11
  • Сообщений: 7

Re: Поиск цикла

Конечно цикл - компонента сильной связности, я их как-то даже не ассоциировал, и вообще, они ищутся дольше - 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 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Поиск цикла

Обычно при компайл эрроре пишут еще и сообщение об ошибке. Полезно бывает его прочитать и разобраться, в чем дело.

Ну и не видя условия тяжело что-то сказать. Возможно, где-то в нем кроется какое-то дурацкое ограничение из-за которого код падает.

7 Ответ от Coder

  • Coder
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-09-11
  • Сообщений: 7

Re: Поиск цикла

Сообщение о конкретной ошибке не пишут.
Условие лаконичное: дан ориентированный невзвешенный граф, требуется найти любой цикл и вывести его в порядке обхода цикла. (1<=n<=10^5;1<=m<=10^5).
Условие почти дословно.
Код  стал падать когда добавилась процедура print(), выводящая цикл и завершающая программу(видимо криво завершается).

8 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Поиск цикла

На всех нормальных онлайн джаджах при ошибке компиляции выдает лог компилятора. Нужно его только поискать.

Код не может падать при ошибке компиляции, т.к. он даже не запускается.

9 Ответ от Coder Отредактировано Coder (2011-09-15 00:15:05)

  • Coder
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-09-11
  • Сообщений: 7

Re: Поиск цикла

Я имею ввиду, что тот код, что в первом сообщении получает TLE, а если выводить вершины цикла не в конце, а сразу при нахождении и завершать программу(как в сообщении 5), то он не компилится на сервере.
Я решаю на http://neerc.ifmo.ru/president/11/index.html
Могу в личку написать вам пароль.

10 Ответ от Coder

  • Coder
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-09-11
  • Сообщений: 7

Re: Поиск цикла

Написал аналогично на дельфи и сдал.
Медленно работало на c++ видимо из-за векторов для хранения ребер.