关于图存边方式
  • 板块学术版
  • 楼主Shiina_Mahiru
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/1/11 19:57
  • 上次更新2023/10/24 04:42:17
查看原帖
关于图存边方式
897035
Shiina_Mahiru楼主2023/1/11 19:57

一个用 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;
}
2023/1/11 19:57
加载中...