창고로 귀속을 비귀속으로 바꾸다

경기에서 만약에 시스템 창고가 매우 작다면 너무 깊은 귀속은 창고를 넘치게 할 것이다. 이때 우리는 스스로 손으로 창고를 써서 귀속을 수공 창고로 바꾸어야 한다.방법도 사실 매우 간단하다.기본적인 사고방식에서 우리는 끊임없이 팝,push를 사용한다.그런데 언제push, 언제pop?에서 깊이 우선 트리에 대한 설명에서 깊이 트리에서 각 노드를 염색하고 흰색은 방문한 적이 없다.회색은 접근했지만 이 노드의 모든 하위 트리는 아직 접근을 완료하지 못했습니다.검은색, 노드가 접근되었고, 이 노드의 모든 하위 트리가 완전히 접근되었다.그래서 우리는 색깔 표시를 통해 판단했다.전체 프레임은 다음과 같습니다.

memset(vis,0,sizeof(vis));
stack S;
S.push(root)
while(!S.empty()){
    int u = S.top();
    if(vis[u] == 1)// if node is gray, then color black
    {
        vis[u] = 2;
        // do things after dfs children.
        S.pop();
    }
    else if(vis[u] == 0)// if node is white, then color gray 
    {
        vis[u] = 1;
        // do things before dfs children.
        for all children v
            S.push(v);
    }
}