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

P1983 [NOIP2013 普及组] 车站分级

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

RT

#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;
}

求助啊,调不动了/kk


by SIXIANG32 @ 2020-08-03 21:55:53

后面那个输出是调试用的
感觉是连边连错了qwq


by SIXIANG32 @ 2020-08-03 21:57:52

在线等,急!


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

@SIXIANG dfs里不用队列啊,直接递归就可以了


by VioletIsMyLove @ 2020-08-03 22:06:36

能说这拓扑看不懂吗。。。


by SIXIANG32 @ 2020-08-03 22:07:07

@axnAyY 啊手残,打的是bfs,函数名写错了


by VioletIsMyLove @ 2020-08-03 22:07:34

仔细一看,车站分级,我去,强悍如斯


by SIXIANG32 @ 2020-08-03 22:08:12

@amhxyp 函数名写错了………………


by VioletIsMyLove @ 2020-08-03 22:10:32

本来说的就不是函数,只是单纯的看不懂,毕竟我太蒟了


by qiuzhehan @ 2020-08-03 22:10:52

for(int i=1;i<=si++)少了;


by VioletIsMyLove @ 2020-08-03 22:11:39

少个;编译怎么过的。。。


| 下一页