一个用 vector,另外一个邻接表存的图,为什么在这个数据下结果不一样呢,其他地方没有区别
邻接表对了,vector 的错了
6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2
#include<iostream>
#include<cstdio>
#include<vector>
const int N=1e3+10;
int stk[N],top,n,m; std::vector<int> e[N],pl;
bool st[N],in_stk[N];
void dfs(int u)
{
stk[++top]=u; in_stk[u]=st[u]=1;
for(int j : e[u])
{
if(st[j])
{
if(in_stk[j])
{
do
{
pl.emplace_back(stk[top]);
} while(j != stk[top--]);
printf("%d\n",(int)pl.size());
for(auto it : pl) printf("%d\n",it);
exit(0);
}
}
else dfs(j);
}
top-- ; in_stk[u]=0;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++)
{scanf("%d%d",&u,&v); e[u].push_back(v);}
dfs(1); puts("-1");
return 0;
}
#include<iostream>
#include<cstdio>
#include<vector>
const int N=1e3+10;
int h[N],ne[N<<1],e[N<<1],idx;
int stk[N],top,n,m; std::vector<int> pl;
bool st[N],in_stk[N];
void dfs(int u)
{
stk[++top]=u; in_stk[u]=st[u]=1;
for(int i=h[u];i;i=ne[i])
{
int j=e[i];
if(st[j])
{
if(in_stk[j])
{
do
{
pl.emplace_back(stk[top]);
} while(j != stk[top--]);
printf("%d\n",(int)pl.size());
for(auto it : pl) printf("%d\n",it);
exit(0);
}
}
else dfs(j);
}
top-- ; in_stk[u]=0;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++)
{scanf("%d%d",&u,&v); ne[++idx]=h[u],e[idx]=v,h[u]=idx;}
dfs(1); puts("-1");
return 0;
}