JDOJ2781 DFS序列


JDOJ上与DFS的优化和高级应用神马的5道题终于已经切完了……虽然比较恶心但是我还是很开心哒23333


JDOJ2781 DFS序列

题目大意:给定一棵以1为根的有根树,输出这棵树的DFS序,要求在输入中后出现的边优先遍历。

这道题看完,哇~这不是Surface Book™题吗……太简单了QwQ于是就飞快地打完了……

瞬间尴尬

于是,就愉快地RE了……起初以为是数组越界了……但是后来学长告诉我其实是爆栈了……

没办法,第一次不用递归达到DFS效果。

直接用数组模拟栈,每次从栈里拿出一个点,像这个点的出边进行遍历,将找到的点推到栈里面去,之后重复操作就可以了。

附AC代码。

#include <cstdio>
 
int n,tot,inx,iny,stack[1000010],top,next[2000010],to[2000010],now[1000010],head[1000010],tail[1000010];
bool use[1000010];
 
void add(int tx,int ty)
{
    ++tot;
    to[tot]=ty;
    if(!head[tx])
    {
        head[tx]=tot;
        tail[tx]=tot;
        return;
    }
    next[tail[tx]]=tot;
    tail[tx]=tot;
}
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;++i)
    {
        scanf("%d%d",&inx,&iny);
        add(inx,iny);
        add(iny,inx);
    }
    stack[++top]=1;
    use[1]=true;
    while(top)
    {
        int tmp=stack[top--];
        printf("%d\n",tmp);
        for(int i=head[tmp];i;i=next[i])
        {
            if(!use[to[i]])
            {
                stack[++top]=to[i];
                use[to[i]]=true;
            }
        }
    }
    return 0;
}

 

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - JDOJ2781 DFS序列


不骗了,不骗了。
A Simple OIer fighting tooth and nail.