这道(水)题对我这种蒟蒻来说真心难……

P1983 [NOIP2013 普及组] 车站分级

vani_prcups @ 2017-09-05 21:51:33

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stack>
using namespace std;
int n,m,f[1005],ff[1005],a[1005][1005],to[1005],visited[1005],maxn;
stack <int> b;
int main()
{
    scanf("%d %d",&n,&m);
    int tt,temp;
    for (int i=1;i<=m;i++)
    {
        memset(f,0,sizeof(f));
        memset(ff,0,sizeof(ff));
        scanf("%d",&tt);
        for (int j=1;j<=tt;j++)
        {
            scanf("%d",&temp);
            f[temp]=1;
            ff[++ff[0]]=temp;
        }
        for (int j=1;j<=ff[0];j++)
        for (int k=1;k<=n;k++)
        if (f[k])a[ff[j]][k]=1,to[k]++;
    }
    for (int i=1;i<=n;i++)
    if (to[i]==0)b.push(i),visited[i]=1;
    while (!b.empty())
    {
        tt=b.top();
        b.pop();
        if (maxn<visited[tt])
        maxn=visited[tt];
        for (int i=1;i<=n;i++)
        {
            if (a[tt][i])
            {
                to[i]--;
                if (visited[i]==0&&to[i]==0)
                {
                    b.push(i);
                    visited[i]=visited[tt]+1;
                }
            }
        }
    }
    printf("%d",maxn);
}

我想通过这种方法判断深度的

结果发现会挂掉

不知大佬们怎么判定深度的?


by vani_prcups @ 2017-10-11 13:45:48

来挖自己的坟贴了……


by bingliang @ 2017-10-12 11:12:09

建图,拓扑,跟你的方法一样吧。 这是正解之一。


|