P5318 【深基18.例3】查找文献（这道题测试样例有bug)

小灰灰 2023-02-13 03:51 31阅读 0赞

题目描述  
小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。

假设洛谷博客里面一共有 n(n\\le10^5)n(n≤10  
5  
) 篇文章（编号为 1 到 nn）以及 m(m\\le10^6)m(m≤10  
6  
) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。

这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。保证编号为 1 的文章没有被其他文章引用。

请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。

> 这道题有个小bug，题目说编号为1的文章不会被其它文章引用，但是测试样例却出现了被编号为1的文章被其它文章引用了。 使用如下代码提交的时候，看wa的点就可以发现这种情况了。 如果1是不会被其它文章引用的话，那么1只会出现一次，因此状态标记可有可无，而下面的代码没标记1就出错了，1再次进行了访问，这就证明了题目确实是有漏洞。

#include<bits/stdc++.h> 
    using namespace std;
    int v[100005];
    vector<int> e[100005];
    void dfs(int cur)
    { 
        cout<<cur<<' ';
        for(int i=0;i<e[cur].size();i++)
        { 
            int search=e[cur][i];
            if(!v[search])
            { 
                v[search]=1;       
                dfs(search);
            }
    
         } 
    }
    void bfs(int cur)
    { 
        int q[100005],f=0,r=0;
        q[r++]=cur;
        v[cur]=1;
        while(f!=r)
        { 
            int tmp=q[f++];//出队 
            cout<<tmp<<' ';
            for(int i=0;i<e[tmp].size();i++)
            { 
                int search=e[tmp][i];
                if(!v[search])
                { 
                    q[r++]=search;
                    v[search]=1;
                }   
            }
        }
    }
    int main()
    { 
        int i,j,n,m,x,y;
        cin>>n>>m;
        for(i=1;i<=m;i++)
        { 
            cin>>x>>y;
            e[x].push_back(y);
        }
        for(i=1;i<=n;i++)
        sort(e[i].begin(),e[i].end());
        dfs(1);
        memset(v,0,sizeof(v));
        cout<<endl;
        bfs(1);
        return 0;
    }

解决办法：标记v\[1\]即可。