1 条题解

  • 0
    @ 2021-6-15 10:09:30

    C++ :

    #include <cstdio>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    /*
    struct queue{
        int head,tail,data[300000];
        void pop(){head++;return;}
        void push(int t){data[++tail]=t;return;}
        int front(){return data[head];}
    };*/
    
    int n,m,ac;
    bool map[2001][2001],check[2001];int indgr[2001],p,path[2001],px[2001][2001];
    
    int main()
    {
    	while(scanf("%d%d",&n,&m)==2)
    	{
    		memset(map,0,sizeof(map));
    		memset(px,0,sizeof(px));
    	    for(int i=1;i<=m;i++)
    	    {
    	        memset(check,0,sizeof(check));
    	        scanf("%d",&p);
    	        for(int j=1;j<=p;j++)
    	        {
    	            scanf("%d",&ac);
    	            path[j]=ac;
    	            check[ac]=1;
    	        }
    	        for(int k=path[1]+1;k<path[p];k++)
    	        {
    	            if(check[k]) continue;
    	            for(int j=1;j<=p;j++)
    	            {
    	                if(!map[k][path[j]])
    	                {
    	                    px[k][++px[k][0]]=path[j];
    	                    map[k][path[j]]=1;
    	                    indgr[path[j]]++;
    	                }
    	            }
    	        }
    	    }
    	    int s=0,sz=0;
    	    queue<int> que;
    	    for(int i=1;i<=n;i++)
    	    {
    	        if(indgr[i]==0)
    	        {
    	            sz++;
    	            que.push(i);
    	        }
    	    }
    	    while(sz!=0)
    	    {
    	        int ck=sz;s++;sz=0;
    	        for(int i=1;i<=ck;i++)
    	        {
    	            int temp=que.front();que.pop();
    	            for(int j=1;j<=px[temp][0];j++)
    	            {
    	                p=px[temp][j];
    	                indgr[p]--;
    	                if(indgr[p]==0)
    	                {
    	                    sz++;
    	                    que.push(p);
    	                }
    	            }
    	        }
    	    }
    	    printf("%d\n",s);
    	}
        return 0;
    }
    
    

    Pascal :

    var n,m,i,j,k,s,x,max:longint;p:array[1..1010,1..1010]of boolean;
        d:array[1..1000]of boolean;kk,c,level:array[1..1010]of longint;
        a:array[0..1010]of longint;
    begin
      read(n,m);
      for i:=1 to m do
        begin
          fillchar(d,sizeof(d),false);
          read(s);
          for j:=1 to s do
            begin
              read(c[j]);
              d[c[j]]:=true;
            end;
          for j:=c[1] to c[s] do
            if d[j]=false then
              begin
                for k:=1 to s do p[c[k],j]:=true;
              end;
        end;
      for i:=1 to n do
        begin
          for j:=1 to n do
            if p[j,i] then inc(kk[i]);
          if kk[i]=0 then
            begin
              inc(a[0]);
              a[a[0]]:=i;
            end;
        end;
      while a[0]>0 do
        begin
          x:=a[a[0]];
          dec(a[0]);
          for i:=1 to n do
            if p[x,i] then
              begin
                if level[x]>=level[i] then level[i]:=level[x]+1;
                dec(kk[i]);
                if kk[i]=0 then
                  begin
                    inc(a[0]);
                    a[a[0]]:=i;
                  end;
              end;
        end;
      for i:=1 to n do
        if level[i]>max then max:=level[i];
      writeln(max+1);
    end.
    
    • 1

    信息

    ID
    314
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者