这道题有个小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;
}