建边求助
查看原帖
建边求助
856309
oiyang楼主2023/8/28 21:01

我一开始用链式前向星建边,然后有WA有T,后来改成vector后就AC了。 为啥?

这是过了的代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;
int ind[maxn];
int n,m,ans;
queue<pair<int,int> >q;
vector<int>line[maxn];
void topo()
{
	for(int i=1;i<=n;i++)
		if(ind[i]==0)
			q.push(make_pair(i,1));
	ans=1;
	while(!q.empty())
	{
		int num=q.front().first,level=q.front().second;
		q.pop();
		for(int i=0;i<(int)line[num].size();i++)
		{
			int v=line[num][i];
			ind[v]--;
			if(ind[v]==0)
			{
				q.push(make_pair(v,level+1));
				ans=max(ans,level+1);
			}
		}
	}
}
bool vis[maxn];
int stop[maxn][maxn];
bool pd[maxn][maxn];
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')
			f=-f;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
			vis[j]=0;
		stop[i][0]=read();
		for(int j=1;j<=stop[i][0];j++)
		{
			int x;
			x=read();
			stop[i][j]=x;
			vis[x]=1;
		}
		for(int j=stop[i][1];j<=stop[i][stop[i][0]];j++)
		{
			if(vis[j])
				continue;
			for(int k=1;k<=stop[i][0];k++)
			{
				if(!pd[j][stop[i][k]])
				{
					ind[stop[i][k]]++;
					line[j].push_back(stop[i][k]);
					pd[j][stop[i][k]]=1;
				}
			}
		}
	}
	topo();
	printf("%d",ans);
	return 0;
}

这是没过的代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;
int ind[maxn];
int head[maxn],cnt;
struct edge{
	int to,pre;
}line[maxn];
void addline(int u,int v)
{
	cnt++;
	line[cnt].to=v;
	line[cnt].pre=head[u];
	head[u]=cnt;
}
int n,m,ans;
queue<pair<int,int> >q;
void topo()
{
	for(int i=1;i<=n;i++)
		if(ind[i]==0)
			q.push(make_pair(i,1));
	ans=1;
	while(!q.empty())
	{
		int num=q.front().first,level=q.front().second;
		q.pop();
		for(int i=head[num];i;i=line[i].pre)
		{
			int v=line[i].to;
			ind[v]--;
			if(ind[v]==0)
			{
				q.push(make_pair(v,level+1));
				ans=max(ans,level+1);
			}
		}
	}
}
bool vis[maxn];
int stop[maxn][maxn];
bool pd[maxn][maxn];
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')
			f=-f;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
			vis[j]=0;
		stop[i][0]=read();
		for(int j=1;j<=stop[i][0];j++)
		{
			int x;
			x=read();
			stop[i][j]=x;
			vis[x]=1;
		}
		for(int j=stop[i][1];j<=stop[i][stop[i][0]];j++)
		{
			if(vis[j])
				continue;
			for(int k=1;k<=stop[i][0];k++)
			{
				if(!pd[j][stop[i][k]])
				{
					ind[stop[i][k]]++;
					addline(j,stop[i][k]);
					pd[j][stop[i][k]]=1;
				}
			}
		}
		
	}
	topo();
	printf("%d",ans);
	return 0;
}
2023/8/28 21:01
加载中...