萌新刚学OI，求助连样例都没过的拓扑排序

SIXIANG32 @ 2020-08-03 21:55:18

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
vector<int>gra[100100];
int d[100100];
int a[100100];
int level[100100];
bool vis[100100];
bool vv[1010][1010];
int n,m,k,ans=0;
void link(int x,int y)
{
    gra[x].push_back(y);
    d[y]++;
}
int dfs()
{
    int tot=0;
    queue<int>que;
    for(int p=1;p<=n;p++)
        if(!d[p])
            que.push(p),level[p]=1;
    while(!que.empty())
    {
        int fr=que.front();
        que.pop();
        tot++;
        for(int p=0;p<gra[fr].size();p++)
        {
            d[gra[fr][p]]--;
            if(!d[gra[fr][p]])
            {
                level[gra[fr][p]]=level[fr]+1;
                ans=max(ans,level[gra[fr][p]]);
                que.push(gra[fr][p]);
            }
        }
    }
    return ans;
}
signed main()
{
    int s;
    cin>>n>>m;
    for(int p=1;p<=m;p++)
    {
        cin>>s;
        for(int i=1;i<=s;i++)
            cin>>a[i];
        for(int i=1;i<=si++)
            for(int j=i+1;j<=s;j++)
                if(!vv[a[i]][a[j]])
                {
                    vv[a[i]][a[j]]=1;
                    link(a[i],a[j]);    
                }
    }
    cout<<dfs()<<endl;
    for(int i=1;i<=n;i++)
        cout<<level[i]<<" ";
    return 0;
}

by VioletIsMyLove @ 2020-08-03 22:25:53

以前码的，码风很差

by VioletIsMyLove @ 2020-08-03 22:26:22

#include <cstdio>
#include <cstring>
using namespace std;
int ans,n,m,ned[1005],tot,a[1005],x,D[1005],U[1005],lnk[1005][1005],son[1005],fa[1005];
bool f[1005][1005],hx[1005],flg;
inline int read()
{
    char ch=getchar(); int res=0;
    while (ch>'9'||ch<'0') ch=getchar();
    while (ch>='0'&&ch<='9') res=res*10+ch-48,ch=getchar();
    return res;
}
inline long long abs(long long x){if (x<0) return -x;return x;}
void work(int x){for (int i=1;i<=fa[x];i++) son[lnk[x][i]]--;}
int main()
{
//  freopen("level.in","r",stdin);
//  freopen("level.out","w",stdout);
    n=read(),m=read();
    for (int i=1;i<=m;i++){
        memset(hx,0,sizeof(hx)),x=read(),D[0]=U[0]=0;
        for (int i=1;i<=x;i++) hx[a[i]=read()]=1;
        for (int i=a[1];i<a[x];i++)
        if (hx[i]) U[++U[0]]=i; else D[++D[0]]=i;
        U[++U[0]]=a[x];
        for (int i=1;i<=D[0];i++)
        for (int j=1;j<=U[0];j++)
        if (!f[D[i]][U[j]])
        f[D[i]][U[j]]=1,son[U[j]]++,lnk[D[i]][++fa[D[i]]]=U[j];
    };
    do {
        flg=tot=0,ans++;
        for (int i=1;i<=n;i++)
        if (!son[i]) son[i]=-1,flg=1,ned[++tot]=i;
        for (int i=1;i<=tot;i++) work(ned[i]);
    } while (flg);
    printf("%d\n",ans-1);
    return 0;
}

by int19260817 @ 2020-08-03 22:57:45

这……

直接粘代码不太好吧

by int19260817 @ 2020-08-03 23:00:39

@SIXIANG 求答案用dfs，不要用bfs。

by SIXIANG32 @ 2020-08-04 10:30:33

@axnAyY 我用bfs不行啊