C#, DFS и Stack Overflow

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

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
09:49:52
Зарегистрироваться »

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

→ Трансляции

Leetcode BiWeekly Contest 144 — Solution Discussion

Shayan

До начала 11:19:52

Codeforces CodeTON Round 9 (Div 1 + Div 2) — Solution Discussion

Shayan

До начала 12:49:52

Всё →

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

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

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

Всё →

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

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

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

→ Прямой эфир

Детальнее →

Блог пользователя 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

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

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

→ Ответить

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

Время на сервере: 23.11.2024 07:45:08 (k3).

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

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