请求小数据hack,实在是调不出来了
查看原帖
请求小数据hack,实在是调不出来了
62573
zzqDeco楼主2020/11/9 20:22

不知道自己代码有啥问题,可以思路就有问题,所以请求hack

#include <cstdio>
#include <queue>
#include <iostream>

using namespace std;

struct edge
{
  int to,next;
}e[1000010];

int n,m;

int head[1000010],num;

int d1[1000010],d2[1000010];

void addedge(int a,int b)
{
  e[++num].to=b;
  e[num].next=head[a];
  head[a]=num;
}

int topsort1()
{
  int maxn=-1,ans=0;
  priority_queue<int>q;
  for(int i=1;i<=n;i++)
    if(d1[i]==0) 
      q.push(-i);
  while(!q.empty())
  {
    int now=-q.top();
    q.pop();
    if(now>maxn) ans++,maxn=now;
    for(int i=head[now];i;i=e[i].next)
    {
      d1[e[i].to]--;
      if(!d1[e[i].to]) q.push(-e[i].to);
    }
  }
  return ans;
}

int f(int x)
{
  if(x>=1000000) return x-1000000;
  return x;
}

int topsort2()
{
  int maxn=-1,ans=1;
  priority_queue<int>q;
  queue<int>q2;
  for(int i=1;i<=n;i++)
    if(d2[i]==0) 
      q.push(i+1000000),maxn=i;
  while(!q.empty())
  {
    int now=f(q.top());
    q.pop();
    if(now>maxn) ans++,maxn=now;
    for(int i=head[now];i;i=e[i].next)
    {
      d2[e[i].to]--;
      if(!d2[e[i].to])
      {
        if(e[i].to<=maxn) q.push(e[i].to+1000000);
        else q.push(e[i].to);
      }
    }
  }
  return ans;
}

int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
  {
    int a,b;
    scanf("%d%d",&a,&b);
    addedge(a,b);
    d1[b]++;
    d2[b]++;
  }
  printf("%d\n%d",topsort1(),topsort2());
}
2020/11/9 20:22
加载中...