我一开始用链式前向星建边,然后有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;
}