C#, DFS и Stack Overflow

→ Обратите внимание

До соревнования
Codeforces Round 959 при поддержке NEAR (Div. 1 + Div. 2)
07:12:53
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3803
2	jiangly	3707
3	Benq	3627
4	ecnerwala	3584
5	orzdevinwang	3573
6	Geothermal	3569
6	cnnfls_csy	3569
8	Radewoosh	3542
9	jqdai0815	3532
10	gyh20	3447

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	awoo	161
2	maomao90	160
3	adamant	157
4	maroonrk	154
5	-is-this-fft-	148
5	SecondThread	148
7	Petr	147
7	atcoder_official	147
9	TheScrasse	145
9	nor	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя Quercitron

C#, DFS и Stack Overflow

Автор Quercitron, 12 лет назад, По-русски

Мои программы на C# с dfs получают Runtime Error, видимо из-за переполнения стека.

Стандартный размер стека у треда в C# -- 1 МБ. Из-за этого программа без изменения размера стека падала на крупных тестах как на сервере, так и у меня локально.

Я прочитал, что новому треду при создании можно попытаться задать максимальный размер. Я увеличил его до 100 МБ, и это решило проблему локально, но на сервере решение продолжает падать. Возможно на сервере не хватает прав на увеличения стека.

Подскажите, пожалуйста, как мне справиться с этой проблемой.

c#, dfs, stack overflow

Quercitron
12 лет назад
22

Комментарии (21)

Показать архивные | Написать комментарий?

it4.kp

12 лет назад, # |

Избавляйтесь от рекурсии. На codeforces стек у C# не увеличить.

→ Ответить

Shaykhutdinov-T-I

12 лет назад, # ^ |

+10

Объясните "синему" (мне) как обходить граф в глубину без рекурсии.

→ Ответить

Fcdkbear

12 лет назад, # ^ |

+11

Моделировать ручной стек.

→ Ответить

gnull

12 лет назад, # ^ |

← Rev. 3 →

+15

stack<int> s;
int first[maxn];//первая не обработанная вершина
bool edge[maxn][maxn];//матрица смежности
int color[maxn];//цвета вершин
const int white=0,gray=1,black=2;
s.push(start);//start - стартовая вершина
while(!s.empty()){
	if( color[s.top()] != white ){
		s.pop();
		continue;
	}
	color[s.top()]=gray;
	for(int i=first[s.top()];i<n;i++){//перебираем исходящие ребра
		first[s.top()]=i+1;//помечаем, что обработали i-тую вершину
		if( edge[s.top()][i] && color[i]==white ){
			s.push(i);//вместо вызова dfs(i)
			i=first[s.top()]-1;//теперь обрабатывается другая вершина, i ставится в начало
		}
	}
	color[s.top()]=black;
	s.pop();
}

→ Ответить

Endou

12 лет назад, # ^ |

BFS же, не?

→ Ответить

gnull

12 лет назад, # ^ |

+18

Это DFS, если заменить stack на queue будет BFS.

→ Ответить

Shaykhutdinov-T-I

12 лет назад, # ^ |

А можете написать реализацию, где при обходе в глубину для вершины вычисляется параметр исходя из таких же параметров сыновей, для конкретности поиск числа потомков для каждой вершины с помощью обхода в глубину (не рекурсивная реализация)?

→ Ответить

gnull

12 лет назад, # ^ |

Тем-же шаманством делаем топологическую сортировку, и находим число потомков начиная с листьев.

→ Ответить

Shaykhutdinov-T-I

12 лет назад, # ^ |

Век живи, век учись, спасибо.

→ Ответить

IlyaCk

12 лет назад, # ^ |

Шаманство в студию!

→ Ответить

Hohol

12 лет назад, # ^ |

← Rev. 2 →

UPD. Гонево какое-то.

→ Ответить

IlyaCk

12 лет назад, # ^ |

← Rev. 2 →

Что это в принципе dfs — разумеется, да. Что он имеет все свойства рекурсивного dfs — разумеется, нет!!!

Присваивание color[s.top()]=black; происходит ДО!!! обработки потомков в дереве dfs. И, например, проверку ацикличности (только сказать "да, цикл есть" или "нет, цикла нету"), в рекурсивном виде имеющую вид

Procedure DFS_cycles(v);
var u;
Begin
  st[v]:=1; 
  for (u : v -> u) do (*перебираємо у змiннiй u всi вершини, куди йдуть дуги з вершини v*)
    if st[u]=0 then 
      DFS_cycles(u)
    else
      if st[u]=1 then
        CYCLE!!! ;
  st[v]:=2;
End;

трудно перевести в вышеупомянутый dfs вида while(!mystack.empty) { ... }

Так что прав Shaykhutdinov-T-I, просящий написать прочие подробности реализации, а не минусующие его.

Лично я вот знаю только один способ — более точно эмулировать рекурсивный dfs, храня в стеке (структуре данных) не просто вершины, а пары "какая вершина; какой по порядку её сосед уже рассмотрен".

→ Ответить

gnull

12 лет назад, # ^ |

Спасибо, исправил.

→ Ответить

IlyaCk

12 лет назад, # ^ |

Что-то я не верю, что такие изменения действительно решили проблему...

→ Ответить

Slamur

12 лет назад, # ^ |

← Rev. 5 →

UPD. Сам дурак.

Вариант с покраской вершин (например, для того же поиска циклов):

stack < int > s;
int color[maxn];
int first[maxn];
bool edge[maxn][maxn];
const int white = 0, grey = 1, black = 2;

s.push(start);
while (!s.empty()){
	int from = s.top;
	if (color[from] == white || color[from] == grey && first[from] < n){	//вершина непомеченна, или еще не из всех ее потомков запускался dfs
		color[from] = grey;
		boolean check = false; // имеется ли соседняя непомеченная вершина
		for (int to = first[from]; to < n; ++to){ // запускаем dfs из всех необработанных соседей вершины
			if (edge[from][to] && color[to] == white){
				q.push(to);
				first[from] = to + 1;
				check = true;
				break;
			}
		}
		if (!check){
			first[from] = n + 1;
		}
	}else{ // вершина помеченна, значит мы в нее пришли уже на выходе из рекурсии из потомков
		// делаем все, что надо делать после выхода dfs из потомков вершины
		
		color[from] = black;
		s.pop();
	}
}

→ Ответить

IlyaCk

12 лет назад, # ^ |

← Rev. 2 →

UPD: это ответ на правку 2, следующие ещё не читал.

Согласен, это тоже можно привести к правильному виду (именно привести, см., например, http://ideone.com/pUkoq ; так как было — неправильно). Я в общем-то и не утверждал, будто необходимо хранить текущую рассматриваемую вершину. Я утверждал, что ранее предложенные развёртывания рекурсии в цикл с использованием вместо программного стека структуры данных стек не умели различать три ситуации:

вершина ещё вообще никак не исследована, в неё ещё не вошли
в вершину вошли, но не вышли (продолжается рассмотрение подграфа, достижимого из неё)
уже произошёл откат рекурсии через эту вершину

(Например, есть граф с рёбрами 1->2, 1->3 и 2->3. Если мы уже посещали вершину 3 через 1->2->3, а потом ещё раз посетили через 1->3, это никоим образом не цикл.). Так что (1) от (2 и 3) надо отличать, чтоб принимать решение, надо ли именно тут продолжать поиск. (2) от (1 и 3) надо отличать, чтоб видеть действительно ли прямо сейчас обнаружен цикл.

Спасибо за указание способа, как это всё же можно сделать.

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

Например, надо опять-таки проверить ацикличность, но если цикл есть, то предъявить его (весь цикл). В реализации, предложенной мной, вершины, составляющие цикл, будут идти в структуре данных стек подряд, а в предложенной Вами — нет.

Например, орграф имеет n-1 дугу, все вида 1->i при i от 2 до n: предложенный Вами способ нарастит размер стека до n, хотя ни рекурсия ни точная её эмуляция так делать не будут.

Так что они скорее альтернативные, каждый имеет достоинства и недостатки.

→ Ответить

NCoder

12 лет назад, # ^ |

← Rev. 2 →

Через стэк. UPD: блин, надо обновлять страничку перед тем, как комментировать -_-

→ Ответить

Quercitron

12 лет назад, # ^ |

+10

Если нельзя увеличить размер стека, то это печаль Не для того я решаю задачи по СП, чтобы писать дфс без рекурсии

→ Ответить

HolyInq

12 лет назад, # ^ |

Не для того я решаю задачи по СП, чтобы получать WA.

→ Ответить

stifff

12 лет назад, # |

Подниму старую тему. Вопросы по С#:

Можно ли как-то увеличить размер стека для рекурсии? (моделировать стек не вариант, т.к. другие языки имеют преимущество)
Как насчет поддержки SortedSet i BigInteger? (добавить в строку компиляции dmcs вместо gmcs)

→ Ответить

og.kostya

6 лет назад, # |

Во время работы c# от Microsoft проблемы со стеком не было, и вот она опять появилась

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 18.07.2024 10:22:07 (h1).

Десктопная версия, переключиться на мобильную.

При поддержке